Our lovely KK has a difficult Social problem.
A big earthquake happened in his area.
$N\left( 2\leq N\leq 2000\right)$ cities have been implicated. All the roads between them are destroyed.
Now KK was commissioned to rebuild these roads.
However, after investigation，KK found that some roads are too damaged to rebuild.
Therefore, there are only $M\left( 0\leq M\leq 15000\right)$ roads can be rebuilt.
KK needs to make sure that there is a way between any two cities, and KK wants to rebuild roads as few as possible.
With rebuilding minimal number of roads, he also wants to minimize the difference between the price of the most expensive road been built and the cheapest one.

The first line of the input file contains an integer $T\left( 1\leq T\leq 10\right)$, which indicates the number of test cases.

For each test case,The first line includes two integers $N\left( 2\leq N\leq 2000\right)$，$M\left( 0\leq M\leq 15000\right)$.

The next $M$ lines include three integers $a,b,c(a\neq b,1\leq c\leq 2*{10}^{9})$,indicating there is a undirected edge between $a$ and $b$,the cost is $c$.

For each test case, output the smallest difference between the price of the most expensive road and the cheapest one.If there is no legal solution, then output -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
2 0

1686
-1

BestCoder Round #71 (div.1)