有一天,已经厌倦了一个人在家的 Pak Chanek 决定去旅行。在寻找合适的地方时,他发现伦敦有一个有趣的结构。
根据 Pak Chanek 收集的信息,编号从 $$$1$$$ 到 $$$N$$$ 的城市有 $$$N$$$。这些城市通过 $$$N-1$$$ 双向道路相互连接,第 $$$i$$$ 条道路连接城市 $$$U_i$$$ 和 $$$V_i$$$,穿越时间为 $$$W_i$$$ 小时。换句话说,Londonesia 的结构形成一棵树。
Pak Chanek 想要在伦敦进行一次旅程,起点和终点在任何城市(不一定是同一个城市),以便用尽可能少的时间至少访问每个城市一次。为了让旅程更快地结束,帕克·查内克还携带了一个即时传送装置,可以从一个城市移动到任何一个城市,最多只能使用一次。帮助 Pak Chanek 找到所需的最短时间。
注意:
- Pak Chanek 只需要每个城市至少访问一次。 Pak Chanek 不必遍历每条路。
- 在旅途中,可以多次访问一座城市或一条道路。
输入
第一行包含一个整数 $$$N$$$ ($$$1 \le N \le 10^5$$$) — 伦敦的城市数量。
接下来的 $$$N-1$$$ 行中的第 $$$i$$$ 包含三个整数 $$$U_i$$$、$$$V_i$$$ 和 $$$W_i$$$ ($$$1 \le U_i, V_i \le N$$$, $$$1 \le W_i \le 10^9$$$) — 连接的双向道路城市 $$$U_i$$$ 和 $$$V_i$$$ 需要 $$$W_i$$$ 小时才能穿越。伦敦西亚的道路形成一棵树。
输出
输出一个整数,表示每个城市至少访问一次所需的最短时间(以小时为单位)。
示例
输入 #1
4 1 2 4 2 3 5 3 4 4
输出 #1
8
输入 #2
5 1 2 45 1 3 50 1 4 10 1 5 65
输出 #2
115
注意
在第一个示例中,时间最短的旅程是 $$$2 → 1 \xrightarrow{\text{teleport}} 4 → 3$$$。
在第二个示例中,时间最短的旅程是 $$$3 → 1 → 4 → 1 → 2 \xrightarrow{\text{teleport}} 5$$$。