树与哈密顿路径 2

题目描述

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

道路 $i$ 双向连接城市 $A_i$ 和 $B_i$,长度为 $C_i$。任意两个城市都可以通过若干条道路相互到达。

求从某个城市出发,利用道路访问所有城市至少一次所需的最短旅行距离。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

4
1 2 2
1 3 3
1 4 4

11

若按 $4 \to 1 \to 2 \to 1 \to 3$ 旅行,总距离为 $11$,这是最小值。

注意无需返回出发城市。

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

数据范围

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

提示

注意答案可能会超过 32 位整数的范围(参见样例 2)。