Problem: On the xy-plane, Snuke is going to travel from the point (x_s, y_s) to the point (x_t, y_t). He can move in arbitrary directions with speed 1. Here, we will consider him as a point without size.

There are N circular barriers deployed on the plane. The center and the radius of the i-th barrier are (x_i, y_i) and r_i, respectively. The barriers may overlap or contain each other.

A point on the plane is exposed to cosmic rays if the point is not within any of the barriers.

Snuke wants to avoid exposure to cosmic rays as much as possible during the travel. Find the minimum possible duration of time he is exposed to cosmic rays during the travel.

Constraints

* All input values are integers.
* -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

Input

The input is given from Standard Input in the following format:


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


Output

Print the minimum possible duration of time Snuke is exposed to cosmic rays during the travel. The output is considered correct if the absolute or relative error is at most 10^{-9}.

Examples

Input

-2 -2 2 2
1
0 0 1


Output

3.6568542495


Input

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


Output

0.0000000000


Input

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


Output

4.0000000000

Solution (in PYTHON3):

Solution:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt
from heapq import heappush, heappop

# node class
class Node(object):
    def __init__(self, num, x, y, r):
        self.num = num
        self.x = x
        self.y = y
        self.r = r
        
# graph class
class Graph(object):
    def __init__(self, num):
        self.graph = [[] for _ in range(num)]
        self.nodes = []
        
    # 辺の長さを調べる
    def calc_edge_len(self, node1, node2):
        dist = sqrt((node1.x - node2.x)**2 + (node1.y - node2.y)**2) - node1.r - node2.r
        if dist <= 0:
            return 0
        else:
            return dist
        
    # 辺を追加する
    def add_edge(self, node1, node2):
        edge_len = self.calc_edge_len(node1, node2)
        self.graph[node1.num].append((edge_len, node2.num))
        self.graph[node2.num].append((edge_len, node1.num))
    
    def get_graph(self):
        return self.graph

# ダイクストラ法
def dijkstra(graph:list, node:int, start:int, goal:int) -> int:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    visited = [False]*node
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        if visited[cur_node]:
            continue
        
        visited[cur_node] = True
        
        if cur_node == goal:
            return dist[goal]
        
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist[goal]

# input
xs, ys, xt, yt = li()
n = ni()

# グラフにスタートとゴールを追加
g = Graph(n+2)
g.nodes.append(Node(0,xs,ys,0))
g.nodes.append(Node(1,xt,yt,0))

# グラフにそれぞれのバリアを追加
for i in range(n):
    x,y,r = li()
    g.nodes.append(Node(i+2,x,y,r))

# バリアを結ぶエッジを追加していく
for i in range(len(g.nodes)):
    for j in range(i+1, len(g.nodes)):
        g.add_edge(g.nodes[i], g.nodes[j])
        
graph = g.get_graph()

# 隣接リストをダイクストラに放り込む
dist = dijkstra(graph, n+2, 0,1)

print(dist)