3278. hcy226 的蜜月计划

单点时限: 2.0 sec

内存限制: 256 MB

闻闻薰衣草的香味,就可以知道情人有多爱你。
与其说薰衣草是开在田野中大片大片的紫,飘在空中的香,不如说是记忆里的东西。
收割薰衣草,如同收割幸福的爱情。
陶醉在紫色的花海中,爱情如此甜蜜。
风起的时候,薰衣草的味道总会飘近身边。
阳光下的香味,弥漫着思念。
记忆就象薰衣草,一起走过的爱情不能忘。
——英国民谣《薰衣草》(节选)

hcy226 带着他的女朋友来到了法国美丽的普罗旺斯,顺着这美丽的薰衣草的花海,他们准备游览 $N$ 个不同的城市。

这 $N$ 个城市之间一共有 $N-1$ 条道路。他们此时在最北边的一座城市,准备在玩一遍所有的城市之后,再回到最北边的那一座城市。数据保证每个城市都是可以到达的。(编号为 1 的城市为最北方的城市)

他们希望这一次的旅行不要浪费太多的时间在路上,所以请你帮他们算一算,游玩这么多城市在路上最少需要消耗多少时间。

输入格式

第一行一个整数 $N$ $(2 \leq N \leq 200~000)$,表示城市的数量。

接下来一共 $N-1$ 行。每行三个整数 $s,t,l$ $(1 \leq s, t \leq N, 1 \leq l \leq 1~000)$,表示一条道路,$s, t$ 分别为两座城市的编号,$l$ 为这条道路的长度。

输出格式

一个整数,表示游览 $N$ 座城市在路上花费的最少时间。

样例

Input
5
1 2 5
1 5 2
1 3 4
3 4 6
Output
34

209 人解决,217 人已尝试。

231 份提交通过,共有 447 份提交。

1.6 EMB 奖励。

创建: 7 年,6 月前.

修改: 6 年,5 月前.

最后提交: 1 月,3 周前.

来源: 2017 ACM 「一场」测验赛