P17641 [ICPC 2019 Yinchuan R] Toad's Travel

一只蟾蜍正在 Byteland 旅行，Byteland 由若干城市和若干道路组成，每条道路连接一对城市。更具体地说，Byteland 的地图是一个无向连通边带权图，其中每条边最多位于一个简单环上。蟾蜍最初在编号为 $1$ 的城市，并希望至少经过所有道路一次。 **时间就是金钱！** 蟾蜍必须最小化他旅行路径的总长度。

第一行包含两个整数 $n, m~(2 \le n \le 10^5, n-1 \leq m \leq 2n-2)$，表示 Byteland 中的城市数量和道路数量。 接下来的 $m$ 行，每行包含三个整数 $u_i, v_i, w_i~(1 \le u_i, v_i \le n, u_i \ne v_i, 0 \le w_i \le 10^5)$，表示一条长度为 $w_i$ 的道路连接城市 $u_i$ 和 $v_i$。保证任意一对城市之间最多只有一条道路。

输出一个整数，表示可能的最小总和。

在样例测试中，一条最佳路径为 $$\displaystyle 1\rightarrow2\rightarrow6\rightarrow2\rightarrow3\rightarrow4\rightarrow5\rightarrow3\rightarrow1$$ 该路径的总长度为 $8$。 翻译由 DeepSeek V4 Pro 完成