103614: [Atcoder]ABC361 E - Tree and Hamilton Path 2

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.

问题陈述

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

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

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

限制条件

• $2 \leq N \leq 2\times 10^5$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_i \leq 10^9$
• 所有输入值都是整数。
• 任何两个城市都可以通过某些道路相互到达。

输入

输入从标准输入以以下格式给出：

$N$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$

输出

打印答案。

示例输入1

4
1 2 2
1 3 3
1 4 4

示例输出1

11

如果你按$4 \to 1 \to 2 \to 1 \to 3$旅行，总旅行距离为11，这是最小的。

注意你不需要返回起始城市。

示例输入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

示例输出2

9000000000

注意溢出问题。