问题描述

在 $x$-$y$ 平面上，高濑要从点 $(x_s, y_s)$ 前往点 $(x_t, y_t)$。他可以以速度 $1$ 在任意方向上移动。在这里，我们将他视为一个没有大小的点。

平面上部署了 $N$ 个圆形屏障。第 $i$ 个屏障的中心和半径分别为 $(x_i, y_i)$ 和 $r_i$。这些屏障可能重叠或包含彼此。

如果平面上的一个点不在任何屏障内，那么它就会受到宇宙射线的照射。

高濑希望在旅行过程中尽量避免宇宙射线的照射。找出他在旅行过程中可能暴露在宇宙射线下的最短时间。

约束条件

• 所有输入值都是整数。
• $-10^9 ≤ x_s, y_s, x_t, y_t ≤ 10^9$
• $(x_s, y_s)$ ≠ $(x_t, y_t)$
• $1≤N≤1,000$
• $-10^9 ≤ x_i, y_i ≤ 10^9$
• $1 ≤ r_i ≤ 10^9$

输入

输入以以下格式从标准输入给出：

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

$N$

$x_1$ $y_1$ $r_1$

$x_2$ $y_2$ $r_2$

$:$

$x_N$ $y_N$ $r_N$

输出

打印出高濑在旅行过程中可能暴露在宇宙射线下的最短时间。如果绝对或相对误差至多为 $10^{-9}$，则输出是正确的。

示例输入 1

-2 -2 2 2
1
0 0 1

示例输出 1

3.6568542495

一条最优路径如下：

示例输入 2

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

示例输出 2

0.0000000000

一条最优路径如下：

示例输入 3

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

示例输出 3

4.0000000000

一条最优路径如下：