解题思路
路网是树。从队部出发要覆盖全部结点、最后不必返回，每条边至少走一次，但通往「从 1 出发最远的那个结点」的那条链不用折返。
- 把边权和记为 S。若每条边都走一个来回，总路程是 2S，这对应「走遍后再回到 1」。
- 现在允许停在任意结点，最优是停在距 1 最远的结点，少走一段长度为 D 的返程，其中 D 是从 1 出发的最大距离。
- 因此答案为 2S−D。
- 从 1 做一次树遍历即可同时得到 S 与 D。边权可达 109，点数可达 105，要用 64 位整数。
题目内容
林场巡护队要把辖区内全部哨所走一遍。辖区里一共有 m 个哨所，编号为 1 到 m，队部设在 1 号哨所。哨所之间由 m−1 条小路连成一棵树：任意两个哨所都能互相到达，并且没有回路。每条小路有一个非负长度。
巡护从队部出发，必须到达每一个哨所至少一次；全部走完后不必返回队部。沿小路可以来回走。求完成这次巡护所需的最短总路程。
形式化地：给定一棵 m 个结点的无向树，边权为非负整数。从结点 1 出发，找一条（可重复走边）的途径，使得每个结点至少出现一次，最小化途径上边权之和。
输入描述
第一行一个整数 m（1≤m≤100000），表示哨所个数。
接下来 m−1 行，每行三个整数 u,v,c（1≤u,v≤m，0≤c≤1000000000），表示 u 号与 v 号哨所之间有一条长度为 c 的小路。
输入保证这些小路构成一棵树。
输出描述
输出一个整数，表示最短巡护路程。
样例1
输入
4
1 2 1
1 3 2
3 4 3
输出
7
说明
边权之和为 6。从队部出发到最远哨所 4 的距离是 5。每条小路除了通往最远哨所的那条链外都要走一个来回，因此最短路程为 2×6−5=7。一条走法是 1→2→1→3→4。
样例2
输入
2
1 2 10
输出
10
说明
只有一条小路。走到 2 号哨所即可结束，不必返回，路程为 10。
样例3
输入
6
1 2 5
2 3 5
1 4 1
4 5 1
4 6 100
输出
123
说明
边权之和为 112，从 1 出发最远到达 6，距离 101。最短路程为 2×112−101=123。
数据范围
- 1≤m≤100000
- 0≤c≤1000000000
- 共 m−1 条边，构成一棵树
- 所有输入均为整数
