问题 25511 --最小差值生成树

25511: 最小差值生成树

时间限制: 1 Sec  内存限制: 128 MB
提交: 53  解决: 30
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][340kb]

题目描述

CodeWaySky很早就学了最小生成树,所以CodeWaySky现在对简单的求最小生成树不感兴趣了。现在CodeWaySky想知道,对于一个给定的图,它的所有生成树中,最大边和最小边的边权差最小是多少。
因为CodeWaySky这个技术人员实在太忙了,到处帮大家解决问题,无法脱身,所以这个问题就交给你来解决了。

输入

第一行,两个用空格隔开的整数 N 和 M,分别表示顶点数和边数。
下面 M 行,每行 3 个数 u,v,w,表示 u 和 v 之间有一条权值为 w 的无向边。

输出

一行,一个非负整数,表示最大边和最小边的最小边权差。
若图本身不连通,则输出-1

样例输入

4 5 
1 2 3 
1 3 5 
1 4 6 
2 4 6 
3 4 7

样例输出

1

提示

【数据范围】

20%    M<=200

100%     2<=N<=100, 0<=M<=5000

来源

[提交][状态]