10906: ABC361 - E - Tree and Hamilton Path 2
[Creator : ]
Description
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.
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.
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}$
```
```
$N$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$
```
Output
Print the answer.
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.
- $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.
Sample 1 Input
4
1 2 2
1 3 3
1 4 4
Sample 1 Output
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 2 Input
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 2 Output
9000000000
Beware overflow.