Розміщення сервера

В місті є спеціальна комп’ютерна мережа, яка використовується для передачі інформації військовими. У зв’язку з частими ракетними обстрілами інфраструктура країни зазнала значних пошкоджень. Разом з цим виникли проблеми функціонування комп’ютерної мережі в межах міста.

Відомою є інформація про початкову структуру комп’ютерної мережі та час передачі інформації між відповідними вузлами мережі. Відомо, що якщо між вузлами існує зв’язок, то інформація досягається найбільш вигідним (швидким) маршрутом.

Після виникнення пошкоджень мережі час передачі інформації між деякими вузлами зменшився.

Визначте, де потрібно розмістити головний сервер, щоб час передачі інформації від сервера до найвіддаленішого (того, до якого інформація находить найбільш повільно) вузла мережі був би мінімальним.

Вхідні дані

Перший рядок містить два натуральних числа: n (1 ≤ n ≤ 1000) - кількість вузлів мережі та m - кількість каналів зв’язку між цими вузлами.

У кожному з наступних m рядків наведено інформацію про кількість мілісекунд c[i] на передачу інформації від вузла a[i] до b[i] у формі трьох чисел: a[i], b[i] та c[i] (1 ≤ a[i], b[i] ≤ n, 1 ≤ i ≤ m).

У наступному рядку розміщено число k (0 ≤ k ≤ m) - кількість каналів зв’язку, у яких зменшилась швидкість передачі інформації.

Далі розміщено k рядків, у кожному з яких наведено інформацію на скільки зменшився час на передачу інформації між відповідною парою вузлів у формі трьох чисел: x[i], y[i] та z[i] (1 ≤ x[i], y[i] ≤ n, 1 ≤ i ≤ m), де x[i], y[i] - номери вузлів мережі, а z[i] показує, на скільки мілісекунд збільшився час передачі інформації між вузлами x[i] та y[i].

Вихідні дані

Визначте, у якому вузлі мережі потрібно розмістити головний сервер, щоб час передачі інформації від сервера до найвіддаленішого (того, до якого інформація находить найбільш повільно) вузла мережі був би мінімальним. Якщо сервер можна розмістити в декількох вузлах, то перерахуйте номери таких вузлів у порядку зростання.

Приклади

Примітка

Сервер варто розмістити в пункті 1. Тоді час передачі даних до найбільш відділеного вузла 4 буде складати 25 мілісекунд.