Holey Road

You are driving a tiny remote controlled car along a road in very bad condition. The road is full of holes. The car cannot drive over a hole, because it would fall in and be damaged beyond repair. Driving off the road is not allowed either, because the tall grass around the road would swallow the car for good.

The car is so small that you can treat it as a point with no size. The road is $W$ meters wide and $L$ meters long, and it runs parallel to the $y$ axis. The car starts at $(W/2, 0)$ and has to reach $(W/2, L)$. Every hole is a perfect circle. No hole overlaps or touches another hole, and no hole touches the edge of the road. The car may graze the boundary of a hole.

Find the length of the shortest route to the destination that avoids the holes.

The first line contains the number of test cases $T$.

The first line of each test case contains three integers $N$, $W$, $L$: the number of holes, the width of the road, and the length of the road. Each of the next $N$ lines contains three integers $x_i$, $y_i$, $r_i$ describing a hole whose centre is $(x_i, y_i)$ and whose radius is $r_i$.

• $0 < T \le 100$
• $0 \le N \le 100$
• $0 < L \le 1000$
• $0 < W \le 100$
• $r_i < x_i < W - r_i$
• $r_i < y_i < L - r_i$
• $0 < r_i < \min(\lfloor W/2 \rfloor, \lfloor L/2 \rfloor)$

For each test case, print on one line the length of the shortest route from the start to the destination that avoids the holes. Round the length to exactly six digits after the decimal point.