/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
AtCoder国には 1 から N の番号がついた N 個の街と 1 から N-1 の番号がついた N-1 本の道路があります。
道路 i は街 A_i と街 B_i を双方向に結び、長さは C_i です。どの街同士も、いくつかの道路を通って互いに行き来することができます。
いずれかの街を出発し、道路による移動で全ての街を 1 度以上訪れるための移動距離の最小値を求めてください。
制約
- 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
オーバーフローに注意してください。
Score : 500 points
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.