В Бертауне собираются открыть кафе известной сети БерДональдс. При этом очень важно правильно выбрать месторасположение нового кафе, чтобы до него было удобно добираться. Система дорог Бертауна представляет собой n перекрестков, соединенных m двусторонними дорогами. Для каждой дороги известна ее длина. Также известно, что от каждого перекрестка по дорогам можно добраться до любого другого.
Ваша задача — найти такое расположение кафе, при котором кратчайшее расстояние по дорогам от кафе до самого дальнего перекрестка будет минимально. Учтите, что кафе может находиться не только на перекрестке, но и в любой точке любой дороги.
Выходные данные
Выведите единственное вещественное число — кратчайшее расстояние от оптимального положения кафе до самого дальнего перекрестка. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не превосходит 10 - 9.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 2 1
|
0.50
|
|
2
|
3 3
1 2 1
2 3 1
1 3 1
|
1.00
|
|
3
|
3 2
1 2 100
2 3 1
|
50.50
|