Sensor Network

A building is guarded by a set of sensors. Each sensor controls exactly two distinct doors, and every door is controlled by at least one sensor. Think of the doors as the vertices of a graph and the sensors as its edges: the graph is simple, and no two sensors control the same pair of doors.

Each sensor has a recommended voltage written on it. A sensor may run at its recommended voltage or higher — running it above the recommended voltage works but carries an increasing risk of failure — yet it must never run below its recommended voltage. Almost every sensor has a different recommended voltage.

You must switch on a subset of the sensors. A subset is called admissible when it satisfies both of these rules:

• Coverage. Every door is controlled by at least one sensor in the subset.
• Connectivity. Power is fed to one active sensor and then distributed to the others through wires. A wire may only join two active sensors that share a door (two sensors are neighbours when some door is controlled by both). Because every active sensor must receive power, the active sensors must all be reachable from one another through such wires; that is, they must form a single connected group.

All active sensors are supplied the same voltage, which cannot be below any of their recommended voltages. To keep the risk of failure low, the chosen sensors should have recommended voltages that are as close together as possible. Define the margin of a subset as the difference between the largest and the smallest recommended voltage among its sensors.

The full set of sensors is always admissible. Among all admissible subsets, find the smallest possible margin.

The input contains several test cases, separated by single blank lines.

Each test case begins with a line containing the integer $n$ ($2 \le n \le 350$), the number of doors, numbered $0$ through $n-1$. The next line contains the integer $m$ ($n-1 \le m \le n(n-1)/2$), the number of sensors. Each of the next $m$ lines describes one sensor with three integers $a$, $b$ and $w$ ($0 \le a \le n-1$, $0 \le b \le n-1$, $a \ne b$, $1 \le w \le 2^{15}$): the two distinct doors it controls and its recommended voltage. No two sensors control the same pair of doors.

The input ends with a line containing a single $0$.

For each test case, print a single line containing the minimum margin of an admissible subset of the sensors.