在 Leonardo 时代，有一种流行的儿童游戏叫做“珠子与线”（Beads-and-wires）。顾名思义，这个游戏使用珠子和线进行。线有红色或蓝色两种。珠子编号为 $1$ 到 $n$。游戏从一颗珠子开始。从这一刻起，可以通过以下方式添加新珠子：

• Append(w, v)：通过一根红线将一颗新珠子 $w$ 连接到现有的珠子 $v$ 上。
• Insert(w, u, v)：通过将新珠子 $w$ 放置在 $u$ 和 $v$ 之间，用两根新蓝线替换连接现有珠子 $u$ 和 $v$ 的现有红线，从而插入一颗新珠子 $w$；换句话说，现有的红线 $u - v$ 被两根新蓝线 $u - w$ 和 $w - v$ 替换。

每一根线（无论是蓝色还是红色）都有一定的长度。游戏结束时，计算的是所有蓝线长度的总和（红线的长度不计入）：这被称为最终得分。

给定一个由“珠子与线”游戏达到的最终配置，指定了珠子之间是如何连接的，并提供了每根线的长度，但省略了线的颜色。

你需要编写一个程序，找出该配置下可能的最大最终得分。更准确地说，在所有以该配置结束的可行“珠子与线”游戏中，你需要找到一个具有最大最终得分（蓝线长度之和）的游戏，并输出该值。

输入格式

第一行包含一个正整数 $n$ —— 珠子的数量，珠子编号从 $1$ 到 $n$。接下来的 $n - 1$ 行，每行包含 $3$ 个数字：$a_i, b_i$（$1 \le a_i < b_i \le n$）和 $1 \le c_i \le 10000$ —— 表示两个珠子由一根线连接，以及该线的长度。

输出格式

输出一个整数 —— 最大最终得分。

样例

输入 1

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

输出 1

60

输入 2

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

输出 2

140

说明

对于第一个样例测试用例，最终得分 $60$ 可以通过以下方式获得：从单颗珠子 $3$ 开始。

• 将 $5$ 连接到 $3$（使用任意长度的线）。
• 在 $3 - 5$ 的线上插入 $1$（使用长度为 $40$ 和 $20$ 的线）。
• 将 $2$ 连接到 $1$，线长为 $10$。
• 将 $4$ 连接到 $1$，线长为 $15$。

以此方式获得的配置如图所示。可以看出，没有其他方法可以获得相同的配置（颜色除外）且具有更大的最终得分。

对于第二个样例测试用例，以此方式获得的配置如图所示，最终得分为 $140$。

子任务

你的程序将在 $4$ 组输入实例上进行测试，具体如下：

• 子任务 1（13 分）：$1 \le n \le 10$。
• 子任务 2（15 分）：$1 \le n \le 200$。
• 子任务 3（29 分）：$1 \le n \le 10000$。
• 子任务 4（43 分）：$1 \le n \le 200000$。

Figure 1. 配置示例 1