Problem4259--最短的路

4259: 最短的路

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

小明最近迷上了地理，他在家的时候会对着地图一看就是好久。有一天他在观察地图上的某一个区域的时候，发现有一块区域非常的特殊。这块区域一共有n个（n为偶数）城市，在这些城市中有n-1条道路连接，每条道路的长度都不一样。小明现在想把这些城市两两分成一组，当两个城市被分到一组时，小明会计算这两个城市之间的距离。现在小明希望，分完以后n个城市以后，最小的距离和为多少？

Input

第一行输入一个数n，表示城市的数量。(1<=n<=10^4)

接下来输入n-1行，每行输入3个数u,v,w分别表示城市u到城市v存在一条长度为w的边。

(1<=u,v<=n,1<=w<=10^9,其中u不等于v)


Output

输出一个整数，表示最小的距离和。

Sample Input

4
1 2 5
2 3 8
3 4 6

Sample Output

11

HINT

【样例输入2】
6
1 3 5
3 2 3
4 5 4
4 3 9
4 6 10
【样例输出2】
31

Source/Category

 

[Submit] [Status]