|
Два профессора
(Время: 1 сек. Память: 16 Мб Сложность: 45%)
Профессор Флойд и профессор Дейкстра ненавидят друг друга. После переезда университета во вновь отстроенный университетский городок они потребовали себе кабинеты в зданиях, максимально удалённых друг от друга. Вам поручено найти расстояние между двумя такими зданиями.
Иными словами, требуется найти два здания, кратчайший путь между которыми наибольший среди всех пар зданий, и вывести длину этого пути. Так как профессорам иногда все же нужно встречаться, путь между выбранными зданиями должен существовать.
Входные данные
В первой строке входного файла INPUT.TXT находятся два целых числа N и M – количество зданий и количество дорог, соединяющих здания (1 ≤ N ≤ 100, 0 ≤ M ≤ N∙(N−1)/2). Далее в M строках расположены описания дорог: 3 целых числа si, ei, li – здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1 ≤ si, ei ≤ N, 0 ≤ li ≤ 100, дороги двунаправленные).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – искомое расстояние.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 3 2
1 2 1
2 3 2 | 3 |
2 | 3 0 | 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |