题目描述

对于一个给定的无向图，求它的所有生成树中，最大边权与最小边权之差的最小值。

输入格式

输入数据共 $m+1$ 行。第 $1$ 行两个整数 $n$ 和 $m$，用空格隔开，分别表示图的顶点数和边数。接下来 $m$ 行，每行 $3$ 个整数 $u$，$v$，$w$，用空格隔开，表示顶点 $u$ 和顶点 $v$ 之间有一条权值为 $w$ 的无向边。

输出格式

输出一行，一个非负整数，表示所有生成树中，最大边和最小边的最小边权差。若图本身不连通，则输出 $-1$。

样例 #1

输入：

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

输出：

1

样例 #2

输入：

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

输出：

1686

数据范围

对于 $20\%$ 的数据，$n \le 10$；

对于 $100\%$ 的数据，$2 \le n \le 100$，$0 \le m \le 3000$，$0 \le w \le 10^9$。

注意：图中可能存在重边。

保证答案在 64 位整数范围内。