AT_abc361_e · Tree and Hamilton Path 2

题意概述

在 AtCoder 国有 \(N\) 个城市（编号 \(1..N\)）与 \(N-1\) 条双向道路（编号 \(1..N-1\)）。 第 \(i\) 条道路连接城市 \(A_i\) 与 \(B_i\)，长度为 \(C_i\)。整张图连通（任意两城可达），因此它是一棵带权树。

要求：从任意城市出发，沿道路行走，使得每个城市至少访问一次，且不要求回到起点。问所需的最小总路程。

输入格式

N
A_1 B_1 C_1
⋮
A_{N-1} B_{N-1} C_{N-1}

• \(2 \le N \le 2 \times 10^5\)
• \(1 \le A_i, B_i \le N\)
• \(1 \le C_i \le 10^9\)
• 输入为整数，整图连通

输出格式

输出一个整数：最小总路程。

样例 #1

输入

4
1 2 2
1 3 3
1 4 4

输出

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

输出

9000000000

说明：注意使用 64 位整型以防溢出。