3909: 城市

从加里敦大学城市规划专业毕业的小明来到了一个地区城市规划局工作。这 个地区一共有n座城市，n − 1条高速公路，保证了任意两座城市之间都可以通 过高速公路相互可达，但是通过一条高速公路需要收取一定的交通费用。小明 对这个地区深入研究后，觉得这个地区的交通费用太贵。小明想彻底改造这个 地区，但是由于上司给他的资源有限，因而小明现在只能对一条高速公路进行 改造，改造的方式就是去掉一条高速公路，并且重新修建一条一样的高速公路 （即交通费用一样），使得这个地区的两个城市之间的最大交通费用最小（即 使得交通费用最大的两座城市之间的交通费用最小），并且保证修建完之后任 意两座城市相互可达。如果你是小明，你怎么解决这个问题？

输入数据的第一行为一个整数n，代表城市个数。 接下来的n − 1行分别代表了最初的n − 1条公路情况。每一行都有三个整 数u，v，d。u，v代表这条公路的两端城市标号，d代表这条公路的交通费用。 1 ≤ u, v ≤ n, 1 ≤ d ≤ 2000

输出数据仅有一行，一个整数，表示进行了最优的改造之后，该地区两城市 之间最大交通费用。

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

7

数据范围 

对于30%的数据，1 ≤ n ≤ 500

对于100%的数据，1 ≤ n ≤ 5000