P15592 [ICPC 2020 Jakarta R] Cul-De-Sac Parades

特雷安蒂斯是一座美丽的小镇，拥有 $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$），分别表示一条道路以及若该道路被游行路线经过所能增加的幸福感。保证从任意一个路口出发，可以通过一系列道路到达其他任何路口。

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

#### 样例 #1 解释 此为题目描述中的示例。 翻译由 DeepSeek 完成