【fjwc2014】生成树

2014年2月16日1,3440

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

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