242048 - 森林巡护的最短行程

题目描述

一片森林设有 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】

可以沿1→3→1→2→5→2→4行走,经过的道路长度依次为2、2、3、1、1、4,总距离13。该路线到达了全部巡护点,并停在4号点。不存在总距离更短的合法路线。

【样例解释2】

只有出发站一个巡护点,已经完成任务,无需行走。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 5 枚
难度 提高


上一题 下一题