一片森林设有 n 个巡护点,编号为 1 到 n,其中 1 号是出发站。巡护点之间有 n-1 条可以双向通行的道路,每条道路有一个正整数长度。
这些道路使任意两个巡护点之间都能到达,并且不存在环路,也就是说,两点之间只有一条不重复经过巡护点的路线。
巡护员从 1 号点出发,需要至少到达每个巡护点一次。同一条道路允许经过多次,每次都要计入道路长度。完成巡护后,可以停在任意一个巡护点,不要求返回 1 号点。
请计算完成任务所需行走的最短总距离。
输入说明:
第一行一个整数 n。
接下来 n-1 行,每行三个整数 u,v,d,表示巡护点 u,v 之间有一条长度为 d 的双向道路。
n=1 时,没有后续道路输入。
对全部数据,1\le n\le100000,1\le u,v\le n,u\ne v,1\le d\le10^6。保证道路构成题目所述的连通无环结构。
输出要求:
输出一个整数,表示最短总行走距离。
5 1 2 3 1 3 2 2 4 4 2 5 1
13
1
0
可以沿1→3→1→2→5→2→4行走,经过的道路长度依次为2、2、3、1、1、4,总距离13。该路线到达了全部巡护点,并停在4号点。不存在总距离更短的合法路线。
只有出发站一个巡护点,已经完成任务,无需行走。