CF1725J Journey

有一天，Pak Chanek 因为独自在家感到无聊，决定去旅行。在寻找合适的地方时，他发现 Londonesia 有一个有趣的结构。 根据 Pak Chanek 收集到的信息，Londonesia 有 $N$ 个城市，编号从 $1$ 到 $N$。这些城市通过 $N-1$ 条双向道路相连，第 $i$ 条道路连接城市 $U_i$ 和 $V_i$，通行需要 $W_i$ 小时。换句话说，Londonesia 的结构是一棵树。 Pak Chanek 想在 Londonesia 进行一次旅行，起点和终点可以是任意城市（不一定是同一个城市），要求每个城市至少访问一次，并且总用时最少。为了让旅程更快结束，Pak Chanek 还携带了一台瞬间传送装置，可以从任意一个城市瞬间移动到另一个城市，但最多只能使用一次。请帮助 Pak Chanek 计算访问所有城市至少一次所需的最短时间。 注意： - Pak Chanek 只需要每个城市至少访问一次，不需要每条道路都经过。 - 在旅途中，一个城市或一条道路可以被访问多次。

第一行包含一个整数 $N$（$1 \le N \le 10^5$），表示 Londonesia 的城市数量。 接下来的 $N-1$ 行中，第 $i$ 行包含三个整数 $U_i$、$V_i$ 和 $W_i$（$1 \le U_i, V_i \le N$，$1 \le W_i \le 10^9$），表示一条连接城市 $U_i$ 和 $V_i$ 的双向道路，通行需要 $W_i$ 小时。Londonesia 的道路结构是一棵树。

输出一个整数，表示访问每个城市至少一次所需的最短时间（单位：小时）。

在第一个样例中，最短的旅行路线是 $2 \to 1 \xrightarrow{\text{传送}} 4 \to 3$。 在第二个样例中，最短的旅行路线是 $3 \to 1 \to 4 \to 1 \to 2 \xrightarrow{\text{传送}} 5$。 由 ChatGPT 4.1 翻译