题目描述

小 s 最近学了最小生成树，不过聪明的小 s 显然对简单的求最小生成树不感兴趣。

现在小 s 想知道，对于一个给定的图，它的所有生成树中，最大边和最小边的边权差最小是多少。

输入格式

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

输出格式

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

input

span1.in
4 5
1 2 3
1 3 5
1 4 6
2 4 6
3 4 7

output

span1.out
1

span2.in

5 10
1 2 9384
1 3 887
1 4 2778
1 5 6916
2 3 7794
2 4 8336
2 5 5387
3 4 493
3 5 6650
4 5 1422

span2.out
1686

数据规模与约定

20% N<=10

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

时间限制：1s

空间限制：256MB