题目描述

小 s 最近学了最小生成树，不过聪明的小 s 显然对简单的求最小生成树不感兴趣。现在小 s 想知道，对于一个给定的图，它的所有生成树中，最大边和最小边的边权差最小是多少。

输入格式

第一行，两个用空格隔开的整数 N 和 M，分别表示顶点数和边数。

下面 M 行，每行 3 个数 u，v，w，表示 u 和 v 之间有一条权值为 w 的无向边。

输出格式

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

span1.in

4 5

1 2 3

1 3 5

1 4 6

2 4 6

3 4 7

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