Description

For a complete graph $G$, if there is exactly one minimum spanning tree $T$, then the complete graph $G$ is said to be extended by the tree $T$.

Given a tree $T$, find the complete graph $G$ with the smallest sum of edge weights that can be extended by $T$.

Input Format

The first line contains $N$, the number of vertices in the tree $T$;

The next $N-1$ lines each contain three integers $S_i, T_i, D_i$; describing an edge $(S_i, T_i)$ with weight $D_i$;

It is guaranteed that the input data forms a tree.

Output Format

Output only one number, representing the smallest sum of edge weights for the complete graph $G$.

Sample 1

Add $D(2, 3)=2, D(3, 4)=3, D(2, 4)=3$ to achieve this.

4
1 2 1
1 3 1
1 4 2

12

Data Range and Hints

For $20\%$ of the data, $N\le 10$;
For $50\%$ of the data, $N\le 1000$;
For $100\%$ of the data, $N\le 10^5, 1\le D_i\le 10^5$.