知名快餐店 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