← 返回题目列表

Codeforces · 266/D

D. 伯兰麦当劳

中文机器翻译题面 查看原题

知名快餐店 BerDonalds 即将在 Bertown 开设咖啡馆。重要的是选择新餐厅的位置,以便能够轻松到达那里。 Bertown 道路系统由 n 个交叉路口表示,由 m 个双向道路连接。对于每条路,我们都知道它的长度。我们还知道,我们可以沿着道路从任何路口到达任何其他路口。

你的任务是找到餐厅的位置,使得从咖啡馆到最远路口的道路上的最短距离最小。请注意,餐厅不仅可以位于路口,还可以位于任何道路的任何地点。

输入

第一行包含两个整数 n 和 m ($$2 \leq n \leq 200; n - 1 \leq m \leq \frac{n(n-1)}{2}$$) — 相应的路口数量和道路数量。接下来是 m 行,描述 Bertown 的所有道路。每条道路由三个整数 ai、bi、wi 描述(1 ≤ ai、bi ≤ n、ai ≠ bi;1 ≤ wi ≤ 105),其中 ai 和 bi 是第 i 条道路连接的路口数量,wi 是第 i 条道路的长度。

保证每条路连接两个不同的路口,任意两个路口之间最多有一条路,并且可以从任意路口到达任意一个路口。

输出

打印一个实数——从最佳餐厅位置到最远路口的最短距离。如果答案的绝对或相对误差不超过 10 - 9,则认为答案是正确的。

示例

输入 #1

2 1
1 2 1

输出 #1

0.50

输入 #2

3 3
1 2 1
2 3 1
1 3 1

输出 #2

1.00

输入 #3

3 2
1 2 100
2 3 1

输出 #3

50.50