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

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

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

输入格式

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

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

输出格式

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

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

样例一

input

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

output

2.0

explanation

最优选址为建筑 $1$。到达 $4$ 个建筑的距离分别为 $0,1,2,2$。

样例二

input

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

output

109.0

explanation

最佳选址为 $1$ 到 $5$ 这条边上，距离 $1$ 的距离为 $32$ 的位置。

样例三

见样例数据下载。

限制与约定

对于 10% 的数据，$N\le 80,L_i=1$。

对于 30% 的数据，$N\le 600,L_i\le 100$。

对于 60% 的数据，$N\le 2000,L_i\le {10}^9$。

对于 100% 的数据，$N\le {10}^5,L_i\le {10}^9$。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载