该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

在 \(3030\) 年，C 城治安还是很差。

描述

C 城有 \(N\) 个走私非法物品的团伙，它们之间有密切的交易，他们之间的关系可以看成是一个无向图，每一个团伙可以看成一个节点，两个团伙有交易当且仅当其存在一条路径连接这两个节点。而两个节点之间存在一条长度为 \(x\) 的边则意味着这两个团伙有一条长度为 \(x\) 的商道。

现在的 C 城警局局长小 Z 了解到**所有的团伙都是存在交易的**（即整个图是联通的）。他的任务是：将罪犯团伙打的尽量分散。

小 Z 认为假如一个点被摧毁后使得某些点无法交易，则这个点是值得摧毁的。他希望摧毁所有值得摧毁的点。

摧毁节点的办法是安放一个炸弹，这个过程需要 \(1\) 单位时间，由于技术落后，小 Z 只能步行。我们假定小 Z 可以分身(~~当局长真是可惜了~~)，所以说，您只需要帮小 Z 找到一些路径，使得所有值得摧毁的点联通，这样小 Z 花费的时间就是路径权值之和 \(+\) 摧毁节点的时间了。

时间就是金钱，小 Z 希望您找到一些路径，在满足上述条件的情况下时间尽可能少。

格式

输入格式

第一行是两个数 \(N\) 和 \(M\)，表示节点个数和边的个数。

接下来 \(M\) 行，每行三个数 \(u_i\)，\(v_i\)，\(x_i\) 表示 \(u_i\) 和 \(v_i\) 间有一条长度为 \(x_i\) 的点。

输出格式

一个整数，表示最短时间。

样例

#1

3 2
1 2 233
2 3 233

输出
1

#2

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

输出
5

#3

10 9
1 2 1
2 3 1
2 5 1
4 5 1
5 6 1
6 7 1
5 9 1
8 9 1
9 10 1

输出
7

提示说明

样例 1 解释：

从 2 号节点出发，摧毁 2 号节点，耗时为 \(1\)。

样例 2 解释：

从 2 号节点出发，摧毁 2 号节点，再沿着 2 -> 4 的路径到达 4 号节点，摧毁 4 号节点，最后沿着 4 -> 6的路径到达 6 号节点，摧毁 6 号节点，耗时为 \(5\)