【问题描述】
对于完全图G,若有且仅有一棵最小生成树为T，则称完全图G是树T的扩展出的。给你一 棵树T,找出T能扩展出的边权和最小的完全图G。

【文件输入】
第一行N表示树T的点数。
接下来N-1行：Si，Ti，Di；描述一条边（Si,Ti）权值为 Di。
保证输入数据构成一棵树。

【文件输出】
一个数，表示最小的图G的边权和。

【样例输入】 4 1 2 1 1 3 1 1 4 2

【样例输出】 12

【样例说明】 添加D(2,3)=2,D(3,4)=3,D(2,4)=3即可。

【数据范围】 对于20%的数据，N<=10 对于50%的数据，N<=1000 对于100%的数据，N<=100000，1<=Di<=100000

Sample 1

Input

4
1 2 1
1 3 1
1 4 2

Output

12

【样例说明】
添加D(2,3)=2,D(3,4)=3,D(2,4)=3即可。

Limitation

1s, 128MiB for each test case.
对于20%的数据，N<=10
对于50%的数据，N<=1000
对于100%的数据，N<=100000，1<=Di<=100 000