最小直径生成树

时间限制:10s      空间限制:259MB

题目描述

输入一个无向图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
[数据范围]
0 < M < = 1000
0 < = Z < = 1000

提示

没有写明提示


题目来源

没有写明来源

Menuappsclose