最小直径生成树

给定一个连通无向图 $G=(V,E)$，其中 $W(a,b)$ 表示边 $(a,b)$ 的长度。请在图中选出一棵生成树 $T$，使 $T$ 的直径最小。

树的直径是树上距离最远的两个顶点之间的路径长度。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示图中顶点数和边数。

接下来 $M$ 行，每行包含三个整数 $X$、$Y$ 和 $Z$，表示一条连接顶点 $X$ 和 $Y$、长度为 $Z$ 的无向边，即 $W(X,Y)=Z$。

保证输入的无向图连通。

输出格式

输出一个数，表示生成树的最小直径。

样例输入

3 3
1 2 0
2 3 1
3 1 2

样例输出

1

数据范围

• $1\le N\le 100$，$1\le M\le 1000$；
• $1\le X,Y\le N$，$0\le Z\le 1000$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3 3
1 2 0
2 3 1
3 1 2

输出

1