ОПОРНІ ШКОЛИ
В рамках процесу децентралізації постала задача створення опорних шкіл. В районі є N селищ, деякі з яких з’єднані дорогами. Відомо, які саме селища з’єднані і відстані вздовж відповідних доріг. Потрібно забезпечити можливість доступу учнів усіх селищ району до опорної школи. При цьому, якщо існує декілька маршрутів до школи, то учні добиратимуться по найкоротшому з них. Визначте, в якому селищі потрібно розмістити школу, так, щоб відстань від неї до найдальшого селища була б мінімальною.
Вхідні дані
У першому рядку записані числа N - кількість селищ (2 ≤ N ≤ 1000), M - кількість доріг, довжини яких відомі (2 ≤ M ≤ N(N-1)/2)*.
У наступних M рядках записана інформація про дороги - по 3 числа (два цілих числа - номери селищ, які з’єднані дорогами та одне додатне дійсне - довжина відповідної дороги).
Вихідні дані
У першому рядку виведіть номер селища, у якому потрібно розмістити опорну школу. Якщо є декілька варіантів розміщення школи, то виведіть номери селищ у порядку зростання.
У другому рядку виведіть відстань від школи до найдальшого селища з точністю до 2 знаків.Якщо задача не має розв’язку, то виведіть одне число -1.
Опорну школу варто розмістити у селищі №2. Відстань від нього в інші складатиме:
в №1 - 5 км,
в №3 - 2 км,
в №4 - 5 км.Таким чином, найдальше селище розташоване на відстані 5 км.