Score : $500$ points

问题陈述

在AtCoder国，有$N$个城市，编号从$1$到$N$，以及$N-1$条道路，编号从$1$到$N-1$。

道路$i$双向连接城市$A_i$和$B_i$，其长度为$C_i$。任何一对城市都可以通过一些道路相互到达。

找出从某个城市出发，至少访问所有城市一次，使用道路所需的最小旅行距离。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

In the nation of AtCoder, there are $N$ cities numbered $1$ to $N$ and $N-1$ roads numbered $1$ to $N-1$.

Road $i$ connects cities $A_i$ and $B_i$ bidirectionally, and its length is $C_i$. Any pair of cities can be reached from each other by traveling through some roads.

Find the minimum travel distance required to start from a city and visit all cities at least once using the roads.

Constraints

• $2 \leq N \leq 2\times 10^5$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_i \leq 10^9$
• All input values are integers.
• Any pair of cities can be reached from each other by traveling through some roads.

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $B_1$ $C_1$

$\vdots$

$A_{N-1}$ $B_{N-1}$ $C_{N-1}$

Output

Print the answer.

Sample Input 1

4
1 2 2
1 3 3
1 4 4

Sample Output 1

11

If you travel as $4 \to 1 \to 2 \to 1 \to 3$, the total travel distance is $11$, which is the minimum.

Note that you do not need to return to the starting city.

Sample Input 2

10
10 9 1000000000
9 8 1000000000
8 7 1000000000
7 6 1000000000
6 5 1000000000
5 4 1000000000
4 3 1000000000
3 2 1000000000
2 1 1000000000

Sample Output 2

9000000000

Beware overflow.