题目描述

一只蟾蜍正在 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$。保证任意一对城市之间最多只有一条道路。

输出格式

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

6 7
1 2 1
1 3 1
2 3 1
3 4 1
3 5 1
4 5 1
2 6 1

8

提示

在样例测试中，一条最佳路径为

$$\displaystyle 1\rightarrow2\rightarrow6\rightarrow2\rightarrow3\rightarrow4\rightarrow5\rightarrow3\rightarrow1$$

该路径的总长度为 $8$。

翻译由 DeepSeek V4 Pro 完成