题目描述

王国有 $n$ 座城市与 $n$ 条有长度的街道，保证所有城市直接或间接联通，我们定义王国的直径为所有点对最短距离中的最大值，现因财政危机需拆除一条道路并同时要求所有城市仍然联通，求所有拆除方案中王国直径的最小值。

输入格式

第一行一个整数 $n$，接下来 $n$ 行每行三个整数 $u,v,w$ 表示城市 $u,v$ 之间有一条长度为 $w$ 的道路。

输出格式

一行一个答案，表示所有方案中直径最小值。

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