Description

给定一个无向图，要求图中一个生成树，这个生成树中的最大边和最小边相差最小，输出这个差值

Input

每组测试数据一组样例

每组样例首先输入两个整数n, m (3 ≤ n ≤ 300, 0 < m ≤ n*(n-1)/2)，表示该组样例中点和边的个数，之后每行三个整数x, y, s (0 ≤ x ≤ n-1, 0 ≤ y ≤ n-1, 1 ≤ s ≤ 10000)，表示编号为x和编号为y的点之间有一条长度为s的边相连，保证给定的图联通，任意两点之间只有一条边相连

Output

对于每组样例，首先输出样例编号，之后输出最小差值，具体格式见sample output

Sample Input

3 3

0 1 220

1 2 120

2 0 160

4 5

2 3 80

1 3 80

0 1 180

2 1 200

3 0 140

Sample Output

40

60

注意：样例虽然给出三组输入数据，但是测试数据中每组输入只会有一组测试数据

数据范围              n                          m

1                          ≤10                       ≤45

2                          ≤10                       ≤45

3                          ≤100                     ≤4950

4                          ≤100                     ≤4950

5                          ≤300                     ≤20000

6                          ≤300                     ≤20000

7                          ≤300                     ≤44850

8                          ≤300                     ≤44850

9                          ≤300                     ≤44850

10                         ≤300                     ≤44850

本题与舒适的路线几乎相同