描述

印第安纳·琼斯身处一座在战争中被摧毁的荒废城市。所有房屋的屋顶都已毁坏，只有部分墙壁仍然矗立。地面布满了地雷，在这座城市中唯一安全的移动方式是沿着剩余的墙壁行走。我们这位英雄的任务是营救一名被困在城市中的人。为了在不相连的两面墙壁之间移动，印第安纳·琼斯想到带上一块木板，他可以把木板放置在两面墙壁之间，然后从一面墙壁走到另一面墙壁。

印第安纳·琼斯和被困人员的初始位置都在某些墙壁部分上。此外，墙壁要么是南北走向，要么是东西走向。

你将得到这座城市残骸的地图。你的任务是确定印第安纳·琼斯为了到达被困人员处需要携带的木板的最小长度。

输入

你的程序应该处理多个测试用例。每个测试用例以一个整数 $N$ 开始，表示城市中剩余墙壁部分的数量（$2 \leq N \leq 1000$）。接下来的 $N$ 行描述每一段墙壁。首先出现的墙壁部分是印第安纳·琼斯开始时所在的墙壁部分。第二个出现的墙壁部分是被困人员所在的墙壁部分。每一段墙壁的描述由三个整数 $X$、$Y$ 和 $L$（$-10000 \leq X, Y, L \leq 10000$）组成，其中 $X$ 和 $Y$ 定义了一段墙壁的最南端（对于南北走向的墙壁部分）或最西端（对于东西走向的墙壁部分）。$L$ 的值决定了墙壁的长度和方向：如果 $L \geq 0$，该墙壁部分是东西走向，长度为 $L$；如果 $L < 0$，该墙壁部分是南北走向，长度为 $|L|$。当 $N = 0$ 时，表示输入结束。

输出

对于输入中的每个测试用例，你的程序应该生成一行输出，包含一个实数值，表示印第安纳·琼斯必须携带的木板的长度。长度必须以实数形式打印，保留两位小数，最后一位小数进行四舍五入。输入中不会包含因四舍五入差异而产生显著影响的测试用例。

示例输入

14
1 1 5
6 8 2
7 2 -2
5 3 3
2 5 2
2 3 2
2 3 -2
4 3 -2
0 7 1
1 8 2
3 6 -2
4 7 2
6 6 1
6 6 -2
3
-10 0 20
-5 1 10
50 50 100
0

示例输出

1.41
1.00

来源

2002 年南美洲竞赛