Slim Span

Given an undirected weighted graph $G$, you must find one of its spanning trees as specified below.

The graph $G$ is an ordered pair $(V, E)$, where $V$ is a set of vertices $\{v_1, v_2, \dots, v_n\}$ and $E$ is a set of undirected edges $\{e_1, e_2, \dots, e_m\}$. Each edge $e \in E$ has a weight $w(e)$.

A spanning tree $T$ is a tree (a connected subgraph without cycles) that connects all $n$ vertices with $n - 1$ edges. The slimness of a spanning tree $T$ is defined as the difference between the largest weight and the smallest weight among the $n - 1$ edges of $T$.

Figure 5: A graph $G$ and the weights of the edges.

For example, a graph $G$ in Figure 5(a) has four vertices $\{v_1, v_2, v_3, v_4\}$ and five undirected edges $\{e_1, e_2, e_3, e_4, e_5\}$. The weights of the edges are $w(e_1) = 3$, $w(e_2) = 5$, $w(e_3) = 6$, $w(e_4) = 6$, $w(e_5) = 7$, as shown in Figure 5(b).

Figure 6: Examples of the spanning trees of $G$.

There are several spanning trees for $G$. Four of them are depicted in Figure 6(a)-(d). The spanning tree $T_a$ in Figure 6(a) has three edges whose weights are $3$, $6$, and $7$; the largest weight is $7$ and the smallest is $3$, so the slimness of $T_a$ is $4$. The slimnesses of the spanning trees $T_b$, $T_c$, and $T_d$ shown in Figure 6(b), (c), and (d) are $3$, $2$, and $1$, respectively. You can easily see that the slimness of any other spanning tree is at least $1$, so the spanning tree $T_d$ in Figure 6(d) is one of the slimmest spanning trees, with slimness $1$.

Your job is to write a program that computes the smallest slimness.

The input consists of multiple datasets, followed by a line containing two zeros separated by a space. Each dataset has the following format.

n m
a1 b1 w1
...
am bm wm

Every input item in a dataset is a non-negative integer, and items on a line are separated by a space.

$n$ is the number of vertices and $m$ the number of edges. You may assume $2 \le n \le 100$ and $0 \le m \le n(n - 1)/2$. Each $a_k$ and $b_k$ ($k = 1, \dots, m$) is a positive integer at most $n$, representing the two vertices $v_{a_k}$ and $v_{b_k}$ connected by the $k$-th edge $e_k$. Each $w_k$ is a positive integer at most $10000$, the weight of $e_k$. You may assume the graph $G = (V, E)$ is simple: it has no self-loops (edges connecting a vertex to itself) and no parallel edges (two or more edges whose endpoints are the same pair of vertices).

For each dataset, if the graph has spanning trees, print the smallest slimness among them. Otherwise, print $-1$. The output must not contain extra characters.