一只蟾蜍正在拜特兰（Byteland）旅行，这里有一些城市和道路，每条道路连接一对城市。具体来说，拜特兰的地图是一个无向连通带权图，其中每条边最多位于一个简单环上。蟾蜍最初位于编号为 1 的城市，它希望至少经过所有的道路一次。

时间就是金钱！

蟾蜍必须使其旅行路径的总长度最小。

输入格式

第一行包含两个整数 $n, m$ ($2 \le n \le 10^5, n-1 \le m \le 2n-2$)，表示拜特兰的城市数量和道路数量。

接下来的 $m$ 行，每行包含三个整数 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 0 \le w_i \le 10^5$)，表示一条连接 $u_i$ 和 $v_i$、长度为 $w_i$ 的道路。保证每对城市之间最多只有一条道路相连。

输出格式

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

样例

输入 1

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

输出 1

8

说明

在样例测试中，其中一条最优路径为： $1 \to 2 \to 6 \to 2 \to 3 \to 4 \to 5 \to 3 \to 1$ 路径的总长度为 8。