题目描述

小可和小达负责管理一个由多个岛屿组成的群岛。每个岛屿之间可以通过桥梁连接，每座桥梁都有一个建设成本。他们需要选择一些桥梁进行建设，使得所有岛屿都能相互到达，并且建设成本的范围最小化。建设成本的范围定义为所选桥梁中最大成本与最小成本的差值。

输入格式

输入包含多个数据集，每个数据集的第一行包含两个整数$n$和$m$，分别表示岛屿的数量和桥梁的数量。

接下来的$m$行，每行包含三个整数$a_k$、$b_k$和$w_k$，表示岛屿$a_k$和岛屿$b_k$之间有一座成本为$w_k$的桥梁。输入以一行两个零结束。

输出格式

对于每个数据集，如果存在一种桥梁选择方案使得所有岛屿连通，则输出最小的建设成本范围；否则输出$-1$。

样例

4 5
1 2 3
1 3 5
1 4 6
2 4 6
3 4 7
4 6
1 2 10
1 3 100
1 4 90
2 3 20
2 4 80
3 4 40
2 1
1 2 1
3 0
3 1
1 2 1
3 3
1 2 2
2 3 5
1 3 6
5 10
1 2 110
1 3 120
1 4 130
1 5 120
2 3 110
2 4 120
2 5 130
3 4 120
3 5 110
4 5 120
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
5 8
1 2 1
2 3 100
3 4 100
4 5 100
1 5 50
2 5 50
3 5 50
4 1 150
0 0

1
20
0
-1
-1
1
0
1686
50

数据范围

• 岛屿数量$n$：$2 \leq n \leq 100$
• 桥梁数量$m$：$0 \leq m \leq \frac{n(n-1)}{2}$
• 桥梁成本$w_k$：$1 \leq w_k \leq 10000$
• 保证没有重边和自环。