说明

特雷安蒂斯是一座美丽的小镇，拥有 $N$ 个路口（编号从 $1$ 到 $N$），这些路口由恰好 $N-1$ 条道路连接，使得从任意一个路口出发，可以通过一系列道路到达其他任何路口。这种特殊的结构导致特雷安蒂斯中有些路口只与另一个路口相连；这样的路口被称为 cul-de-sac（或称为尽端路口）。

为了活跃城镇气氛，镇长决定在特雷安蒂斯举办一场盛大的游行庆典。由于当地的一些迷信，设计游行路线时需要满足两个约束条件。

1. 每条游行路线必须从一个尽端路口出发，在另一个尽端路口结束，且不得重复经过同一条道路。
2. 任意两条游行路线不得有共享的道路；但共享同一个路口是可以的。

镇长估算出，如果一条游行路线经过连接路口 $u_i$ 和 $v_i$ 的道路，则居民的幸福感将增加 $w_i$。

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

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

:::align{center} :::

如图所示，共有 $7$ 个尽端路口，其编号为 $\{1, 2, 3, 4, 8, 9, 10\}$。在此例中，通过安排以下 $3$ 条游行路线可获得最大幸福感。

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

注意，所有这些路线都起始并结束于尽端路口，且没有两条路线共享同一条道路。这些路线的幸福感总和为 $40 + 90 + 80 = 210$。在该例中，不存在能获得超过 $210$ 幸福感的路线方案。

输入格式

输入第一行包含一个整数 $N$（$2 \leq N \leq 100\,000$），表示特雷安蒂斯的路口数量。接下来 $N-1$ 行，每行包含三个整数 $u_i$、$v_i$、$w_i$（$1 \leq u_i < v_i \leq N$；$1 \leq w_i \leq 10^6$），分别表示一条道路以及若该道路被游行路线经过所能增加的幸福感。保证从任意一个路口出发，可以通过一系列道路到达其他任何路口。

输出格式

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

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

210

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

60

提示

样例 #1 解释

此为题目描述中的示例。

翻译由 DeepSeek 完成