Roads in the Kingdom

**题目描述** 王国有 $n$ 座城市与 $n$ 条有长度的街道，保证所有城市直接或间接联通，我们定义王国的直径为所有点对最短距离中的最大值，现因财政危机需拆除一条道路并同时要求所有城市仍然联通，求所有拆除方案中王国直径的最小值。 **输入格式** 第一行一个整数 $n$，接下来 $n$ 行每行三个整数 $u,v,w$ 表示城市 $u,v$ 之间有一条长度为 $w$ 的道路。 **输出格式** 一行一个答案，表示所有方案中直径最小值。

In the Kingdom K., there are $ n $ towns numbered with integers from $ 1 $ to $ n $ . The towns are connected by $ n $ bi-directional roads numbered with integers from $ 1 $ to $ n $ . The $ i $ -th road connects the towns $ u_{i} $ and $ v_{i} $ and its length is $ l_{i} $ . There is no more than one road between two towns. Also, there are no roads that connect the towns with itself. Let's call the inconvenience of the roads the maximum of the shortest distances between all pairs of towns. Because of lack of money, it was decided to close down one of the roads so that after its removal it is still possible to reach any town from any other. You have to find the minimum possible inconvenience of the roads after closing down one of the roads.

The first line contains the integer $ n $ ( $ 3<=n<=2·10^{5} $ ) — the number of towns and roads. The next $ n $ lines contain the roads description. The $ i $ -th from these lines contains three integers $ u_{i} $ , $ v_{i} $ , $ l_{i} $ ( $ 1<=u_{i},v_{i}<=n $ , $ 1<=l_{i}<=10^{9} $ ) — the numbers of towns connected by the $ i $ -th road and the length of the $ i $ -th road. No road connects a town to itself, no two roads connect the same towns. It's guaranteed that it's always possible to close down one of the roads so that all the towns are still reachable from each other.

Print a single integer — the minimum possible inconvenience of the roads after the refusal from one of the roads.

3
1 2 4
2 3 5
1 3 1

5

5
2 3 7
3 1 9
4 1 8
3 5 4
4 5 5

18