e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

ОПОРНІ ШКОЛИ

ОПОРНІ ШКОЛИ

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

Вхідні дані:

У першому рядку записані числа N — кількість селищ (2N1000), M — кількість доріг, довжини яких відомі (2MN(N-1)/2).

У наступних M рядках записана інформація про дороги — по 3 числа (два цілих числа — номери селищ, які з'єднані дорогами та одне додатне дійсне — довжина відповідної дороги).

Вихідні дані:

У першому рядку виведіть номер селища, у якому потрібно розмістити опорну школу. Якщо є декілька варіантів розміщення школи, то виведіть номери селищ у порядку зростання.

У другому рядку виведіть відстань від школи до найдальшого селища з точністю до 2 знаків. Якщо задача не має розв'язку, то виведіть одне число -1.

z4.jpg

Опорну школу варто розмістити у селищі №2. Відстань від нього в інші складатиме: - в №1 - 5 км, - в №3 - 2 км, - в №4 - 5 км. Таким чином, найдальше селище розташоване на відстані 5 км.

Лимит времени 0.5 секунда
Лимит использования памяти 64 MiB
Входные данные #1
4 4
1 2 93.00
1 3 90.00
2 3 43.00
3 4 92.00
Выходные данные #1
3
92.00