藤藤的庄稼地取得了大丰收，当务之急是在庄稼地中找一个好位置把稻米集中起来（以供观赏）。

藤藤的庄稼地可以看作一个 n 个点（这些点上种着庄稼）、m 条边（庄稼地中的小路）的无向图，每条边有边权（小路的长度），保证图连通。

搬运庄稼是一件费时费力的事，所以集中庄稼的位置应该使得这个位置到其它点的最远距离最小（两个点的距离为它们的最短路）。

注意这个位置可以在点上，也可以在某条边上。

第一行包括两个整数 n, m。

接下来 m 行，每行输入一条边 a_i, b_i, w_i，其中 a_i, b_i 是这条边连接的两个点，w_i 是边权。

输出一个实数，为最小的选择的位置到其他点的最远距离，保留 3 位小数。

样例 1 解释

只有一条长为 1 的边，最优位置是它的中点，最远距离为 0.500。

样例 2 解释

三角形三边等长，三个点两两距离都是 1，把中心放在任意顶点上最远距离都是 1，所以答案是 1.000（放在边中点反而更差，因为到对面顶点的距离大于 1）。

数据范围

• 对于 30\% 的数据，n, m \le 4,\ w_i \le 20；
• 另有 25\% 的数据，m = n - 1（图为树）；
• 对于 60\% 的数据，n, m \le 100,\ w_i \le 1000；
• 对于 100\% 的数据，2 \le n \le 300，n-1 \le m \le \min\left(\frac{n(n-1)}{2}, 2\times10^4\right)，1 \le w_i \le 10^5。

提示

先用 Floyd 求出所有点对的最短路 d_{u,i}。若把中心放在边 (u, v) 上、距 u 为 t 的位置（0 \le t \le \text{len}），则它到 i 的距离是

\min\left(t + d_{u,i},\ \text{len} - t + d_{v,i}\right)

于是「这条边上有没有一个位置使得到所有点距离都不超过 r」等价于：对每个 i，t 不能落在禁止区间 (r - d_{u,i},\ \text{len} + d_{v,i} - r) 里；判断这些区间的并集是否盖满 [0, \text{len}]，排序后线性扫一遍即可。

答案对 r 单调，二分 r。小技巧：把边权先乘 2，这样最优答案一定是 0.5 的整数倍，t 和 r 全程都能用整数处理，避免实数误差。