#1262. 最小直径生成树

最小直径生成树

Description

输入一个无向图G=(V,E),W(a,b)表示边(a,b)之间的长度,求一棵生成树T,使得T的直径最小。树的直径即树的最长链,即树上距离最远的两点之间路径长度。

Format

Input

输入第一行包括两个整数N,M,分别表示点与边的个数。 以下M行,每行3个整数X,Y,Z,描述一条无向边(X,Y),且W(X,Y)=Z。

Output

仅一个数,即最小直径。

Samples

3 3
1 2 0
2 3 1
3 1 2
1

Limitation

[数据范围] 0 < M < = 1000 0 < = Z < = 1000