Treantis 是一个美丽的城镇，拥有 $N$ 个路口（编号从 $1$ 到 $N$），这些路口由恰好 $N-1$ 条道路连接，使得从任何一个路口出发都能通过一系列道路到达其他任何路口。这种特殊的结构使得 Treantis 中存在一些路口，每个路口仅与恰好另一个路口相连；这样的路口在 Treantis 中被称为“死胡同”（cul-de-sac）。

为了活跃城镇气氛，Treantis 的市长决定举办一场盛大的游行庆典。由于 Treantis 的一些迷信说法，在设计游行路线时必须满足以下两个约束：

1. 每场游行都应从一个死胡同出发，在另一个死胡同结束，且不能重复经过同一条道路。
2. 任意两场游行的路径不能共享同一条道路；另一方面，共享同一个路口是没有问题的。

市长估计，如果一场游行经过连接路口 $u_i$ 和路口 $v_i$ 的道路，那么市民的幸福感将增加 $w_i$。

你的任务是帮助市长计算在满足上述两个约束的前提下，通过精心设计游行路线所能获得的最大幸福感。

例如，设 $N = 10$，城镇结构如下图所示。

城镇结构示例

如我们所见，这里有 $7$ 个死胡同，编号分别为 $\{1, 2, 3, 4, 8, 9, 10\}$。在这个例子中，通过运行以下 $3$ 条游行路线可以获得最大幸福感：

• $1 \to 5 \to 8$，幸福感为 $10 + 30 = 40$。
• $2 \to 5 \to 6 \to 9$，幸福感为 $20 + 50 + 20 = 90$。
• $4 \to 7 \to 10$，幸福感为 $40 + 40 = 80$。

观察到所有这些游行都从一个死胡同开始并在另一个死胡同结束，且没有两条游行共享同一条道路。这些游行的总幸福感为 $40 + 90 + 80 = 210$。在这个例子中，没有其他游行方案能产生超过 $210$ 的幸福感。

输入格式

输入的第一行包含一个整数：$N$ ($2 \le N \le 100\,000$)，表示 Treantis 的路口数量。接下来的 $N-1$ 行，每行包含三个整数：$u_i, v_i, w_i$ ($1 \le u_i < v_i \le N; 1 \le w_i \le 10^6$)，表示一条连接路口 $u_i$ 和 $v_i$ 的道路，以及如果该道路被游行经过时增加的幸福感。保证从一个路口出发可以通过一系列道路到达其他任何路口。

输出格式

输出一行一个整数，表示在满足所有约束的前提下，精心设计游行路线所能获得的最大幸福感。

样例

样例输入 1

10
1 5 10
2 5 20
3 6 20
4 7 40
5 6 50
5 8 30
6 7 10
6 9 20
7 10 40

样例输出 1

210

说明 1

这是题目描述中的示例。

样例输入 2

7
1 2 10
1 3 5
2 4 15
2 5 20
3 6 12
3 7 13

样例输出 2

60