Will Indiana Jones Get There?

Indiana Jones is in a deserted city that was annihilated during a war. The roofs of all the houses have been destroyed and only portions of the walls are still standing. The ground is so full of mines that the only safe way to move around the city is to walk over the remaining walls. His mission is to rescue a person trapped in the city.

To move between two walls that are not connected, Indiana Jones carries a wooden board that he can lay between the two walls and cross. Because the board can be placed at the closest point between the two walls, crossing from one wall to another requires a board whose length is at least the minimum distance between the two wall sections. Since Indiana Jones carries only one board, its length must be large enough to cross the largest gap encountered along his route.

Fig. 1: City map with the route used by Indiana Jones

The initial positions of both Indiana Jones and the trapped person lie on some wall section. Moreover, every wall runs either in the South-North direction or the West-East direction.

You are given a map of the city's remaining walls. Determine the minimum length of the wooden board Indiana Jones must carry in order to reach the trapped person. Equivalently, among all routes that walk across walls from the starting wall to the target wall, find the route that minimizes the largest gap that must be crossed, and report that largest gap.

The input consists of several test cases.

Each test case begins with an integer $N$, the number of wall sections remaining in the city ($2 \le N \le 1000$). Each of the next $N$ lines describes one wall section. The first wall section listed is the one Indiana Jones starts on; the second is the one the trapped person stands on.

Each wall section is given by three integers $X$, $Y$, and $L$ ($-10000 \le X, Y, L \le 10000$). The point $(X, Y)$ is the southernmost endpoint for a South-North section and the westernmost endpoint for a West-East section. The value $L$ determines the length and direction of the wall:

• If $L \ge 0$, the section runs West-East with length $L$, i.e. from $(X, Y)$ to $(X+L, Y)$.
• If $L < 0$, the section runs South-North with length $|L|$, i.e. from $(X, Y)$ to $(X, Y+|L|)$.

The input ends with $N = 0$.

For each test case, print on its own line the length of the wooden board Indiana Jones must carry.

Print the length as a real number with two digits after the decimal point, rounding the last digit. The input contains no test cases in which rounding differences are significant.