Розміщення сервера#11337
У місті є спеціальна комп'ютерна мережа, яка використовується військовими для передавання інформації. Унаслідок частих ракетних обстрілів інфраструктура країни зазнала значних пошкоджень, зокрема виникли проблеми з функціонуванням комп'ютерної мережі в межах міста.
Відома початкова структура комп'ютерної мережі та час передавання інформації між відповідними вузлами мережі. Якщо між вузлами існує з'єднання, інформація передається найшвидшим шляхом.
Після пошкодження мережі час передавання інформації між деякими вузлами збільшився.
Визначте, де потрібно розмістити головний сервер, щоб час передавання інформації від сервера до найвіддаленішого (тобто такого, до якого інформація доходить найповільніше) вузла мережі був мінімальним.
Перший рядок містить два натуральних числа (1 \leq n \leq 1000) — кількість вузлів мережі, та — кількість каналів зв'язку між цими вузлами.
Кожен із наступних рядків містить по три числа: a_i, b_i, c_i (1 \leq a_i, b_i \leq n, 1 \leq i \leq m), які означають, що час передавання інформації від вузла a_i до вузла b_i становить c_i мілісекунд.
У наступному рядку задано число (0 \leq k \leq m) — кількість каналів, у яких час передавання інформації збільшився.
Далі йдуть рядків, у кожному з яких по три числа: x_i, y_i, z_i (1 \leq x_i, y_i \leq n, 1 \leq i \leq k), що означає, що час передавання інформації між вузлами x_i та y_i збільшився на z_i мілісекунд.
Визначте, у якому вузлі мережі потрібно розмістити головний сервер, щоб максимальний час передавання інформації від сервера до будь-якого іншого вузла був мінімальним. Якщо таких вузлів кілька, виведіть їхні номери у зростаючому порядку.
Приклад 1
Сервер варто розмістити у вузлі . У цьому випадку час передавання даних до найвіддаленішого вузла становитиме 25 мілісекунд.