eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Пожежне депо

Пожежне депо

Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB

Місто обслуговується декількоми пожежними депо. Деякі жителі поскаржились, що відстань від їхнього будинку до найближчого пожежного депо досить велика і почали вимагати, щоб було збудовано ще одне нове. Необхідно визначити місцезнаходження нового депо так, щоб мінімізувати відстань від невдоволених жителів до найближчих до них депо.

Місто складається максимум з 500 перехресть, з'єднаних дорогами різної довжини. На одному перехресті може зустрічатись не більше 20 доріг. Будинки і пожежніе депо знаходяться на перехрестях (відстань від перехрестя до самого будинку вважається рівним нулю). На кожному перехресті знаходиться як мінімум один будинок. На одному перехресті може знаходитись більш ніж одне пожежне депо.

Вхідні дані

Перший рядок містить два натуральних числа: f, кількість існуючих пожежних депо (f100) та i, кількість перехресть (i500). Перекрестя пронумеровано послідовно числами від 1 до i. Далі йде f рядків, кожен з яких містить номер перехрестя, на якому знаходиться пожежне депо. Кожен з наступних рядків містить три натуральних числа: перші два числа – номери перехресть, які з'єднані дорогою, а третє число – довжина цієї дороги. По всім дорогам можна рухатись в обох напрямкаях, і між довільними двома перехрестями існує шлях.

Вихідні дані

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

Приклад

Вхідні дані #1
1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10
Вихідні дані #1
5