Description:


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

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

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

Input:


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

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

Output:


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

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

Sample Input:


Sample Output:


题解:


这是一棵基环外向树~

如果是一棵树的话答案显然是直径除以2。

现在考虑把环拆开,

嗯比较复杂我不写了,参见这篇博客