题目描述

古时候流行过一种叫「穿珠引线」的孩童游戏，道具只有珠子和两种颜色的线——红线与蓝线。珠子编号为 $1$ 到 $n$。游戏从一颗珠子开始，之后每次用下面两种方式之一添上一颗新珠子：

Append(w, v)：把一颗新珠子 $w$ 与一颗已经在场的珠子 $v$ 用红线连起来。

Insert(w, u, v)：把一颗新珠子 $w$ 嵌入两颗正由红线相连的珠子 $u, v$ 之间——具体做法是拆掉 $u, v$ 之间的红线，再分别用蓝线连上 $u, w$ 与 $w, v$。

每条线都有自己的长度。游戏结束时，最终得分等于所有蓝线长度之和。

现在告诉你游戏结束后的局面：每颗珠子与线的连接关系以及每条线的长度，但不告诉你每条线的颜色。请你写一个程序，算出这个局面可能对应的最大得分，即所有能玩出该局面的玩法中，蓝线总长度的最大值。

输入格式

第一行一个正整数 $n$，表示珠子的数量。珠子从 $1$ 到 $n$ 编号。

接下来 $n - 1$ 行每行三个整数 $a_i, b_i, c_i$。保证 $1 \leq a_i \lt b_i \leq n$，$1 \leq c_i \leq 10000$。表示 $a_i$ 号珠子和 $b_i$ 号珠子间连了长度为 $c_i$ 的线。

输出格式

输出一个整数，表示最大可能得分。

样例

5
1 2 10
1 3 40
1 4 15
1 5 20

60

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

140

提示

【样例描述1】

可以通过如下方式获得 $60$ 分：首先从 $3$ 号珠子开始。

把 $5$ 和 $3$ 连起来。（线长度任意）

在 $3$ 和 $5$ 之间嵌入 $1$。（线长分别为 $40$ 和 $20$）

把 $2$ 和 $1$ 用长度为 $10$ 的线连起来。

把 $4$ 和 $1$ 用长度为 $15$ 的线连起来。

【限制与约定】

第一个子任务共 13 分，满足 $1 \leq n \leq 10$。

第二个子任务共 15 分，满足 $1 \leq n \leq 200$。

第三个子任务共 29 分，满足 $1 \leq n \leq 10000$。

第四个子任务共 43 分，满足 $1 \leq n \leq 200000$。