28756번 - Перерыв на обед 스페셜 저지다국어

문제

Супершпион Лэнс Стерлинг находится в городе и отправляется на задание. Для удобства, введем в городе прямоугольную систему координат, единичный отрезок которой имеет длину один метр. Сейчас Лэнс находится в тайном убежище в точке с координатами $(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}$.

제한

힌트