Sneaking Through the Corridor

Seunghyun keeps his room under tight security. The only way in runs along a corridor packed with sensors, and a sensor sounds the alarm as soon as a person or an object enters its range.

Hyunseok is a very nimble spy. A client hired him to steal a classified document from Seunghyun's room, so he got hold of the corridor blueprint first. From the blueprint he has to decide whether he can walk in himself, and if he cannot, how small a robot he has to send instead.

Hyunseok treats the corridor as a plane. The two walls are the lines $x = 0$ and $x = w$, and sensor $i$ detects everything inside the circle with center $(x_i, y_i)$ and radius $r_i$. A sensor sits against a wall or in the middle of the corridor. The object that travels down the corridor is a circle as well.

The object starts at $y = -\infty$ and has to reach $y = +\infty$ while staying inside the corridor. It must never enter the detection range of a sensor. Touching the boundary of a range is fine.

Given the sensor layout, find the largest radius of a circle that gets through the corridor without setting off an alarm.

The first line has the number of test cases $T$. ($1 \le T \le 100$)

Each test case has this form.

• One line with the corridor width $w$. ($1 \le w \le 100\,000$) The two walls are the lines $x = 0$ and $x = w$.
• One line with the number of sensors $n$. ($0 \le n \le 1\,000$)
• $n$ lines with integers $x$, $y$, $r$, the center of a sensor and the radius of its range. ($0 \le x \le w$, $-100\,000 \le y \le 100\,000$, $1 \le r \le 100\,000$)

The corridor runs forever along $y$, and the end the object starts from and the end it leaves through are both far outside every sensor range.

For each test case print on its own line the largest radius of a circular object that passes the corridor undetected. Assume the object moves with unlimited precision. Print $0$ when nothing can get through.

Round the answer to six decimal places and always print all six digits after the point. An answer of $1.5$ prints as 1.500000, and an answer of $0$ prints as 0.000000.