← 返回题目列表

AtCoder · abc361_e

H. 树和汉密尔顿路径 2

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

在AtCoder的国家里,有 N 城市编号 1 to N 和 N-1 道路编号 1 to 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

小心溢出。