题目描述

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

joisino 姐姐构造出了一个 $N$ 个顶点的完全图。该完全图中顶点 $u$ 和 $v$ 之间的边的长度，等于原树中顶点 $u$ 和 $v$ 之间的最短距离。

joisino 姐姐想知道，这个完全图中所有哈密顿路径（※）里，长度最大的那一个有多长。

请输出 joisino 姐姐构造的完全图中所有哈密顿路径里，最长的那一条的长度。

输入格式

输入通过标准输入以以下格式给出。

$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

输出

38

样例 2

输入

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

输出

132

说明/提示

注释

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

约束条件

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

样例解释 1

考虑哈密顿路径 $5 \to 3 \to 1 \to 4 \to 2$，其长度为 $5 + 8 + 15 + 10 = 38$。无法构造出长度 $39$ 或更长的哈密顿路径，所以本例的答案为 $38$。

由 ChatGPT 5 翻译