시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB51443690.000%

문제

Супершпион Лэнс Стерлинг находится в городе и отправляется на задание. Для удобства, введем в городе прямоугольную систему координат, единичный отрезок которой имеет длину один метр. Сейчас Лэнс находится в тайном убежище в точке с координатами $(x_s, y_s)$, ему требуется добраться до точки с координатами $(x_t, y_t)$. Он может перемещаться со скоростью один метр в секунду в любом направлении. Однако, он очень проголодался, поэтому решил перед заданием заскочить перекусить.

Всего в городе есть $n$ заведений, в которых Лэнс может пообедать. Заведение номер $i$ находится в точке $(x_i, y_i)$, и Лэнс знает, что он проведет в нем ровно $t_i$ секунд. Помогите ему определить минимальное время, которое потребуется, чтобы добраться до точки назначения, зайдя по пути перекусить в одно из заведений.

입력

В первой строке даны четыре целых числа $x_s$, $y_s$, $x_t$ и $y_t$ --- координаты тайного убежища и точки назначения ($|x_s|, |y_s|, |x_t|, |y_t| \le 1\,000$).

В следующей строке дано одно целое число $n$ --- количество заведений, где Лэнс может пообедать ($1 \le n \le 1\,000$).

В следующих $n$ строках дано по три целых числа $x_i$, $y_i$ и $t_i$ --- координаты $i$-го заведения и количество секунд, которое придется потратить, чтобы пообедать в этом заведении ($|x_i|, |y_i| \le 1\,000$; $1 \le t_i \le 1\,000$).

출력

Выведите одно вещественное число --- минимальное количество секунд, которое потребуется Лэнсу, чтобы добраться из убежища до точки назначения, зайдя по пути перекусить. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не будет превышать $10^{-9}$.

예제 입력 1

0 0 10 0
1
5 0 3

예제 출력 1

13.000000000000000

예제 입력 2

0 -5 0 -3
1
0 5 10

예제 출력 2

28.000000000000000

예제 입력 3

0 0 5 5
2
3 3 2
3 4 1

예제 출력 3

8.236067977499790