| Codeforces Round 163 (Div. 2) |
|---|
| Закончено |
В Бертауне собираются открыть кафе известной сети БерДональдс. При этом очень важно правильно выбрать месторасположение нового кафе, чтобы до него было удобно добираться. Система дорог Бертауна представляет собой n перекрестков, соединенных m двусторонними дорогами. Для каждой дороги известна ее длина. Также известно, что от каждого перекрестка по дорогам можно добраться до любого другого.
Ваша задача — найти такое расположение кафе, при котором кратчайшее расстояние по дорогам от кафе до самого дальнего перекрестка будет минимально. Учтите, что кафе может находиться не только на перекрестке, но и в любой точке любой дороги.
В первой строке записаны два целых числа n и m (
) — количество перекрестков и дорог соответственно. Далее следует m строк — описание всех дорог в Бертауне. Каждая дорога описывается тремя целыми числами ai, bi, wi (1 ≤ ai, bi ≤ n, ai ≠ bi; 1 ≤ wi ≤ 105), где ai и bi — номера перекрестков, которые соединяет i-ая дорога, а wi — длина i-ой дороги.
Гарантируется, что каждая дорога соединяет два различных перекрестка, между любыми двумя перекрестками имеется не более одной дороги, и от любого перекрестка можно добраться до любого другого.
Выведите единственное вещественное число — кратчайшее расстояние от оптимального положения кафе до самого дальнего перекрестка. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не превосходит 10 - 9.
2 1
1 2 1
0.50
3 3
1 2 1
2 3 1
1 3 1
1.00
3 2
1 2 100
2 3 1
50.50
