题目描述

小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。

快餐店的顾客分布在城市 C 的 \(N\) 个建筑中，这 \(N\) 个建筑通过恰好 \(N\) 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。

现给定城市 C 的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。

输入

第一行，包含一个整数 \(N\)，表示城市 C 中的建筑和道路数目。

接下来 \(N\) 行，每行 \(3\) 个整数 \(A_i,B_i,L_i\), (\(1 \leq i \leq N\); \(L_i > 0\)) 表明一条道路连接了建筑 \(A_i\) 与 \(B_i\)，其长度为 \(L_i\)。

输出

仅包含一个实数，四舍五入保留恰好一位小数，表示最佳快餐店选址距离最远用户的距离。

注意：你的结果必须恰好有一位小数，小数位数不正确不得分。

样例1

输入

4
1 2 1
1 4 2
1 3 2
2 4 1

输出

2.0

说明

如图所示，最优选址为建筑 \(1\)。到达 \(4\) 个建筑的距离分别为 0，1，2，2。

样例 2

输入

5
1 5 100
2 1 77
3 2 80
4 1 64
5 3 41

输出

109.0

说明

如图。

样例 3

见 Download Files: foodshop.in 与foodshop.out。

数据范围限制

对于 \(10\%\) 的数据，\(N \leq 80\)，\(L_i=1\)；
对于 \(30\%\) 的数据，\(N \leq 600\)，\(L_i \leq 100\)；
对于 \(60\%\) 的数据，\(N \leq 2000\),\(L_i \leq 10^9\)；
对于 \(100\%\) 的数据，\(N \leq 10^5\),\(L_i \leq 10^9\)。

限制

每个测试点时限：2秒
内存限制：512MB

来源

NOI2013 D2T3