Пожежна станція#1059
У місті розташовано декілька пожежних станцій. Деякі мешканці скаржаться, що відстань від їхніх будинків до найближчої пожежної станції занадто велика, і вимагають побудувати нову пожежну станцію. Місце для нової станції слід обрати так, щоб максимальна відстань від будь-якого перехрестя до найближчої станції була мінімальною.
У місті не більше перехресть, які з'єднані дорогами різної довжини. До одного перехрестя може прилягати не більше доріг. Будинки та пожежні станції розташовані лише на перехрестях (відстань від перехрестя до будівлі вважається нульовою). На кожному перехресті є принаймні один будинок. На одному перехресті може бути більше ніж одна пожежна станція.
У першому рядку містяться два додатних числа: (f \leq 100) — кількість існуючих пожежних станцій, та (i \leq 500) — кількість перехресть. Перехрестя пронумеровано від до . Наступні рядків містять номери перехресть, на яких розташовані пожежні станції. Кожен з наступних рядків містить три додатних числа: номери двох перехресть, з'єднаних дорогою, і довжину цієї дороги. Всі дороги двосторонні, та між будь-якими двома перехрестями існує маршрут.
Виведіть одне число — найменший номер перехрестя, на якому слід побудувати нову пожежну станцію, щоб мінімізувати максимальну відстань від будь-якого перехрестя до найближчої пожежної станції.
Приклад 1