Description

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

Input Format

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

Output Format

一个数，表示最小的图G的边权和。

Sample

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

样例输出
12

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

Hint

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