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