有 $N$ 座城市，编号为 $1$ 到 $N$，城市之间修建了 $N-1$ 条双向道路。任意两座城市之间都可以互相到达，因此城市和道路组成一棵树。第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$，长度为 $C_i$。

小泽可以任选一座城市作为起点，也可以在任意一座城市结束行程。途中允许多次经过同一座城市或同一条道路，但必须至少访问每一座城市一次。

请计算满足这些要求时，整个行程可能达到的最短总路程。

输入格式

第一行输入一个整数 $N$，表示城市数量。

接下来 $N-1$ 行，第 $i$ 行输入三个整数 $A_i,B_i,C_i$，表示城市 $A_i$ 与城市 $B_i$ 之间有一条长度为 $C_i$ 的双向道路。

输出格式

输出一个整数，表示访问所有城市至少一次所需的最短总路程。

10
1 7 98470976
4 3 882527346
9 1 982238986
1 2 548648467
5 1 751677340
10 1 467050362
8 6 477036513
3 2 98320565
6 1 682677550

7288085769

7
1 3 753077668
4 3 887999497
2 1 203276010
5 7 908033280
5 2 98746776
6 1 197505539

3246144309

6
4 2 659560046
1 3 409023298
3 6 356677668
2 1 708110747
1 5 92254044

2317879847

数据范围与约定

• $2\le N\le2\times10^5$
• $1\le C_i\le10^9$
• 道路构成一棵树