AT_agc018_d [AGC018D] Tree and Hamilton Path

有一棵包含 $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 姐姐构造的完全图中哈密顿路径的最大长度。

### 注释 一个图的哈密顿路径，是指经过图中每个顶点恰好一次的路径。 ### 约束条件 - $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 翻译