瓦莱里安被沙普尔捕获。这场胜利是如此伟大,以至于沙普尔决定在山上雕刻一幅瓦莱里安失败的场景。所以他必须找到最好的地方,让自己的胜利永恒!
他决定走遍波斯的所有n个城市,寻找最好的山峰,但在最近的战争之后,他太累了,不想走太多路。所以他想以尽可能小的遍历次数,至少访问这 n 个城市中的每一个。波斯城市之间有双向道路相连。您可以使用这些道路从任何城市前往任何其他城市,并且每两个城市之间都有一条独特的路径。
所有城市编号为 1 到 n。 Shapur 目前位于城市 1,他希望以尽可能少的行程访问所有其他城市。他可以在任何城市完成他的旅行。
帮助 Shapur 找出他应该旅行多少距离。
输入
第一行包含一个自然数 n (1 ≤ n ≤ 105) — 城市数量。
接下来的 n - 1 行包含 3 个整数,每个 xi、yi 和 wi (1 ≤ xi, yi ≤ n, 0 ≤ wi ≤ 2 × 104)。 xi 和 yi 是一条路的两端,wi 是该路的长度。
输出
一个整数,Shapur 行程的最小长度。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cout (也可以使用 %I64d)。
示例
输入 #1
3 1 2 3 2 3 4
输出 #1
7
输入 #2
3 1 2 3 1 3 3
输出 #2
9