题目描述

在 $xy$ 平面上，尘希望从 $(x_s, y_s)$ 移动到坐标 $(x_t, y_t)$。尘可以以速度 $1$ 向任意方向移动。

平面上有 $N$ 个圆形屏障。第 $i$ 个屏障的圆心为 $(x_i, y_i)$，半径为 $r_i$。这些屏障之间可能会重叠，也可能互相包含。

不在任何一个屏障内部的区域会被宇宙射线照射，尘希望在移动过程中尽可能少地暴露在宇宙射线下。请你求出尘在移动过程中暴露在宇宙射线下的最短时间。

限制条件

• 所有输入均为整数。
• $-10^9 \leq x_s, y_s, x_t, y_t \leq 10^9$
• $(x_s, y_s) \neq (x_t, y_t)$
• $1 \leq N \leq 1,000$
• $-10^9 \leq x_i, y_i \leq 10^9$
• $1\ \leq r_i \leq 10^9$

输入格式

输入以如下格式从标准输入读入。

$x_s$ $y_s$ $x_t$ $y_t$

$N$

$x_1$ $y_1$ $r_1$

$x_2$ $y_2$ $r_2$

$\cdots$

$x_N$ $y_N$ $r_N$

输出格式

请输出尘在移动过程中暴露在宇宙射线下的最短时间。只要绝对误差或相对误差不超过 $10^{-9}$，即可视为正确。

输入输出样例 #1

输入 #1

-2 -2 2 2
1
0 0 1

输出 #1

3.6568542495

输入输出样例 #2

输入 #2

-2 0 2 0
2
-1 0 2
1 0 2

输出 #2

0.0000000000

输入输出样例 #3

输入 #3

4 -2 -2 4
3
0 0 2
4 0 1
0 4 1

输出 #3

4.0000000000

样例解释 1

例如，可以如图所示进行移动。

样例解释 2

例如，可以如图所示进行移动。

样例解释 3

例如，可以如图所示进行移动。