2611 - 最小差值生成树

给定一个点标号从 1到 n 的、有 m 条边的无向图,求边权最大值与最小值的差值最小的生成树。图可能存在自环。

输入

第一行有两个整数,表示图的点数 n 和边数 m。 接下来 m 行,每行三个整数 u,v,w,表示存在一条连接u,v 长度为 w 的边。

输出

输出一行一个整数,表示生成树的最长边和最短边的差值。

样例

输入

4 6 
1 2 10 
1 3 100 
1 4 90 
2 3 20 
2 4 80 
3 4 40 

输出

20
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题