问题描述

有一棵含有 $N$ 个顶点的树，编号从 $1$ 到 $N$。在这棵树中，第 $i$ 条边连接着顶点 $A_i$ 和 $B_i$，并且长度为 $C_i$。

Joisino 创建了一个含有 $N$ 个顶点的完全图。在该图中，连接顶点 $u$ 和 $v$ 的边的长度等于上述树中顶点 $u$ 和 $v$ 之间最短距离。

Joisino 希望知道在这个完全图中最长哈密顿路径（见注释）的长度。找出该路径的长度。

注释

在图中，哈密顿路径 是指访问每个顶点恰好一次的路径。

约束条件

• $2 ≤ N ≤ 10^5$
• $1 ≤ A_i < B_i ≤ N$
• 给定的图是一棵树。
• $1 ≤ C_i ≤ 10^8$
• 所有输入值均为整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $:$ $A_{N-1}$ $B_{N-1}$ $C_{N-1}$

输出

打印出 Joisino 创建的完全图中最长哈密顿路径的长度。

示例输入1

5
1 2 5
3 4 7
2 3 3
2 5 2

示例输出1

38

哈密顿路径 $5$ → $3$ → $1$ → $4$ → $2$ 的长度是 $5+8+15+10=38$。由于图中不存在长度为 $39$ 或更长的哈密顿路径，所以答案是 $38$。

示例输入2

8
2 8 8
1 5 1
4 8 2
2 5 4
3 8 6
6 8 9
2 7 12

示例输出2

132