题目描述

输入一个无向图 $G=(V,E)$，$w(a,b)$ 表示边 $(a,b)$ 之间的长度，求一棵生成树 $T$，使得 $T$ 的直径最小。

树的直径即树的最长链，即树上距离最远的两点之间路径长度。

输入格式

输入第一行包括两个整数 $n,m$，分别表示点与边的个数。

以下 $m$ 行，每行 $3$ 个整数 $x,y,z$，描述一条无向边 $(x,y)$，且 $w(x,y)=z$。

输出格式

仅一个数，即最小直径。

样例输入

3 3
1 2 0
2 3 1
3 1 2

样例输出

1

数据规模与约定

对于 $100\%$ 的数据，保证 $0< m\leq 10^3$，$0\leq z\leq 10^3$。