Problem G
Getting Through

A long and straight corridor is fitted with a number of sensors. Each sensor has a certain range within which it can detect objects or persons. If a part of an object is within the sensor’s range, an alarm will go off. Otherwise, nothing will happen.

Ethan needs to traverse this corridor in order to do some spy stuff at the other end. The question is, can he pass through the corridor without being detected? Can he fit so easily that he can bring some equipment along, or does he have to wear some tight clothing? Or can he perhaps send a robot through instead?

We model the corridor as being two-dimensional (we ignore the height), bounded by two straight lines. Each sensor is located inside the corridor or on a wall. Their scopes are well in between the two ends of the corridor. We model the person or robot going through as a circle. Given the layout, what is the maximum radius this circle can have so that it is possible to negotiate the corridor without being detected?

Figure 1: A visual representation of the samples.

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:

• one line with a single integer $w$ ($1 \leq w \leq 100\, 000$): the width of the corridor. The two walls are given by the lines $x=0$ and $x=w$.

• one line with a single integer $n$ ($0 \leq n \leq 1\, 000$): the number of sensors in the corridor.

• $n$ lines with three space-separated integers $x$, $y$ and $r$ ($0 \leq x \leq w$, $-100\, 000 \leq y \leq 100\, 000$ and $1 \leq r \leq 100\, 000$): the location and the range of each sensor, respectively.

The two ends of the corridor are at $y=-\infty $ and $y=+\infty $, or in less technical terms, they are far beyond the scope of all the sensors.

Output

Per test case:

• one line with one floating point number: the radius of the largest circular object (or person) that could pass through the corridor without being detected, assuming the object can (be) move(d) with absolute precision. If nothing could possibly get through, the output should be zero. The number should be accurate up to $10^{-6}$ absolute precision.

3
10
2
2 0 3
7 12 4
10
2
2 0 3
7 8 4
10
2
2 0 3
7 4 4

1.5
1.216991
0