22485_ABitDifferen

MST (Minimum Spanning Tree) is a common problem in graph theory. It is too easy for all of you. Now there is a problem a bit different.

Given a weighted graph G(V, E), if T is a spanning trees of G.

Define value(T) = max{ value(e) | e is in T } - min{ value(e) | e is in T }

In this problem, you only have to output the minimum value(T).

The first line of the input is a positive integer C, denoting the number of test cases followed.

The first line of each test case is two positive integers N ( 2 < N ≤ 200 ) and M ( M ≤ 5000 ), which represent the number of vertices and edges of G. After that, there are M lines followed. The i-th ( 1 ≤ i ≤ M ) line contains three integers X_i ( 0 < X_i ≤ N ), Y_i ( 0 ≤ Y_i ≤ N ), D_i ( 0 < D_i ≤ 10⁸ ), which means that there is an edge from X_i to Y_i and the distance of this edge is D_i. You can assume that the graph G is connected and no more than one edge exists between any two vertices.

The output should consists of C lines, one line for each test case, only containing one integer which represents the minimum value of value( T ). No redundant spaces are needed.

1
3 3
1 2 10
1 3 20
2 3 30

10