问题1193--定都

1193: 定都

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MB

题目描述

伟大的bxdd即将要成立黄渡王国了!黄渡王国有n个城市。由于王国草创,这n个城市之间只有n-1条道路相连,任意两个城市之间的路径都是唯一的。
王国的建设过程中,必然会对交通系统提出很高的要求。每条道路都有其运输能力上限w。我们定义任意两座城市x与y之间的运输容量S(x,y)为x到y的唯一路径上的道路运输能力的最小值。
现在,bxdd希望选择一个城市作为黄渡王国的首都,使得它到其他所有城市的运输容量之和最大。伟大的bxdd当然知道怎么做了,但是他想要考一考你。

输入

第一行一个整数n(1≤n2×105),表示城市的数量。 
接下来n-1行,每行三个整数u,v,w (1≤u,v≤n, 1w≤1000),表示有一条连接u和v、运力为w的道路。 
保证任意两个城市能互相到达

输出

输出一个整数,表示首都到其他所有城市的运输容量之和的最大值。

样例输入 Copy

4
1 2 2
2 4 1
2 3 1

样例输出 Copy

4

来源/分类