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}.

-----Sample Input-----
-2 -2 2 2
1
0 0 1

-----Sample Output-----
3.6568542495

An optimal route is as follows:

Difficulty: competition

Starter code:

Solutions:
def main():
    import sys
    input = sys.stdin.readline

    import heapq
    def dijkstra_heap(s,g,edge):
        #始点sから各頂点への最短距離
        d = [10**20] * (n+2)
        used = [True] * (n+2) #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        sx,sy,sr=edge[s][0],edge[s][1],edge[s][2]
        for i in range(n+2):
            x,y,r=edge[i][0],edge[i][1],edge[i][2]
            dist=((x-sx)**2+(y-sy)**2)**(1/2)
            heapq.heappush(edgelist,(max(dist-r-sr,0),i))
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            v = minedge[1]
            if not used[v]:
                continue
            d[v] = minedge[0]
            used[v] = False
            bx,by,br=edge[v][0],edge[v][1],edge[v][2]
            for i in range(n+2):
                x,y,r=edge[i][0],edge[i][1],edge[i][2]
                dist=((x-bx)**2+(y-by)**2)**(1/2)
                if used[i]:
                    heapq.heappush(edgelist,(max(dist-r-br,0)+d[v],i))
            if not used[g]:
                break
        return d[g]

    sx,sy,gx,gy = map(int,input().split()) #n:頂点数　w:辺の数
    n=int(input())
    edge=[(sx,sy,0),(gx,gy,0)]
    for i in range(2,n+2):
        x,y,r=map(int,input().split())
        edge.append((x,y,r))
    print(dijkstra_heap(0,1,edge))

def __starting_point():
    main()
__starting_point()

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def dijkstra(n, s, cost):
    res = [f_inf] * n
    res[s] = 0
    checked = [False] * n
    while True:
        v = -1
        for k in range(n):
            if (not checked[k]) and (v == -1):
                v = k
            elif (not checked[k]) and res[k] < res[v]:
                v = k
        if v == -1:
            break
        checked[v] = True
        for m in range(n):
            res[m] = min(res[m], res[v] + cost[v][m])
    return res


def resolve():
    def calc_dist(x1, y1, x2, y2):
        return pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5)

    sx, sy, gx, gy = list(map(int, input().split()))
    n = int(input())
    node = [[sx, sy, 0]] + [list(map(int, input().split())) for _ in range(n)] + [[gx, gy, 0]]
    cost = [[0] * (n + 2) for _ in range(n + 2)]
    for i in range(n + 2):
        x1, y1, r1 = node[i]
        for j in range(i + 1, n + 2):
            x2, y2, r2 = node[j]
            dist = max(0, calc_dist(x1, y1, x2, y2) - (r1 + r2))
            cost[i][j] = dist
            cost[j][i] = dist

    res = dijkstra(n + 2, 0, cost)
    print((res[-1]))


def __starting_point():
    resolve()

__starting_point()

import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from heapq import heapify,heappop,heappush
def dijkstra(G,s = 0): #sを始点とした最短経を求める
    n = len(G)
    dist = [INF] * n
    dist[s] = 0
    q = [(0,s)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for e,cost in G[v]:
            if dist[e] > dist[v] + cost:
                dist[e] = dist[v] + cost
                heappush(q,(dist[e],e))
    return dist

from math import hypot
def main():
    sy,sx,gy,gx = map(int,input().split())
    N = int(input())
    circles = [(sy,sx,0)] + [tuple(map(int,input().split())) for _ in range(N)] + [(gy,gx,0)]
    N += 2

    G = [[] for _ in range(N)]
    for i in range(N):
        x,y,z = circles[i]
        for j in range(i + 1,N):
            p,q,r = circles[j]
            d = max(0,hypot(x - p,y - q) - z - r)
            G[i].append((j,d))
            G[j].append((i,d))
    
    dist = dijkstra(G)
    ans = dist[-1]
    print(ans)
def __starting_point():
    main()
__starting_point()

import sys
input=sys.stdin.readline
sx,sy,tx,ty=list(map(int,input().split()))
n=int(input())
p=[(sx,sy,0)]
for _ in range(n):
  x,y,r=list(map(int,input().split()))
  p.append((x,y,r))
p.append((tx,ty,0))
n+=2
edge=[[]for _ in range(n)]
for i in range(n-1):
  for j in range(i+1,n):
    sx,sy,sr=p[i]
    tx,ty,tr=p[j]
    t=(abs(sx-tx)**2+abs(sy-ty)**2)**0.5
    c=max(0,t-(sr+tr))
    edge[i].append((j,c))
    edge[j].append((i,c))
from heapq import heappop,heappush
inf=10**20
ans=[inf]*n
ans[0]=0
root=[-1]*n
h=[(0,0)]
while h:
  c,v=heappop(h)
  if ans[v]<c:continue
  for u,t in edge[v]:
    if c+t<ans[u]:
      ans[u]=c+t
      root[u]=v
      heappush(h,(c+t,u))
print((ans[n-1]))


import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def dijkstra(n, s, cost):
    res = [f_inf] * n
    res[s] = 0
    checked = [False] * n
    while True:
        v = -1
        for k in range(n):
            if (not checked[k]) and (v == -1):
                v = k
            elif (not checked[k]) and res[k] < res[v]:
                v = k
        if v == -1:
            break
        checked[v] = True
        for m in range(n):
            res[m] = min(res[m], res[v] + cost[v][m])
    return res


def resolve():
    def calc_dist(x1, y1, x2, y2):
        return pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5)

    sx, sy, gx, gy = list(map(int, input().split()))
    n = int(input())
    node = [[sx, sy, 0]] + [list(map(int, input().split())) for _ in range(n)] + [[gx, gy, 0]]
    cost = [[0] * (n + 2) for _ in range(n + 2)]
    for i in range(n + 2):
        x1, y1, r1 = node[i]
        for j in range(i + 1, n + 2):
            x2, y2, r2 = node[j]
            dist = max(0, calc_dist(x1, y1, x2, y2) - (r1 + r2))
            cost[i][j] = dist
            cost[j][i] = dist

    res = dijkstra(n + 2, 0, cost)
    print((res[-1]))


def __starting_point():
    resolve()

__starting_point()

import numpy as np
from scipy.spatial.distance import cdist
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

xs, xy, xt, yt = map(int, input().split())
N = int(input())
barriers = np.array([(xs, xy, 0), (xt, yt, 0)] + [tuple(map(int, input().split())) for _ in range(N)])
dist = cdist(barriers[:, :2], barriers[:, :2])
dist = np.maximum(dist - barriers[:, 2] - barriers[:, 2][:, None], 0)

length = dist.ravel()
frm = np.repeat(np.arange(N + 2), N + 2)
to = np.tile(np.arange(N + 2), N + 2)

matr = csr_matrix((length, (frm, to)), shape=(N + 2, N + 2))
ans = dijkstra(matr, indices=0)[1]
print(ans)

from heapq import heappop, heappush
from math import sqrt
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

INF = 10**15

def dijkstra(E, s, g):
    d = [INF] * len(E)
    d[0] = 0

    queue = []
    heappush(queue, (0, s))

    while queue:
        dist_v, v = heappop(queue)
        if dist_v > d[v]:
            continue
        
        for e, w in E[v]:
            tmp = d[v] + w
            if tmp < d[e]:
                d[e] = tmp
                heappush(queue, (tmp, e))
    
    return d[g]


def main():
    x_s, y_s, x_t, y_t = list(map(int, readline().split()))
    N,*xyr = list(map(int, read().split()))

    XYR = []
    XYR.append((x_s, y_s, 0))
    XYR.append((x_t, y_t, 0))
    for x, y, r in zip(*[iter(xyr)]*3):
        XYR.append((x, y, r))
    
    E = [[] for _ in range(N+2)]
    for i in range(N+1):
        x_i, y_i, r_i = XYR[i]
        for j in range(i+1, N+2):
            x_j, y_j, r_j = XYR[j]
            d = sqrt((x_i - x_j)**2 + (y_i - y_j)**2)
            d -= r_i + r_j
            d = max(0, d)
            E[i].append((j, d))
            E[j].append((i, d))

    ans = dijkstra(E, 0, 1)
    print(ans)


def __starting_point():
    main()

__starting_point()

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

xs,ys,xt,yt = list(map(int,readline().split()))
n, = list(map(int,readline().split()))

xyr = [tuple(map(int,readline().split())) for _ in range(n)] + [(xs,ys,0),(xt,yt,0)]


"""
d: 隣接行列に対する Dijkstra
O(N^2)
"""
def Dijkstra_matrix(d,start):
    n = len(d)
    #INF = 1<<61
    INF = float("inf")
    dist = d[start][:] #startからの最短距離

    used = [0]*n # 最短距離が決まった頂点
    used[start] = 1
    for _ in range(n-1):
        d0  = INF
        idx = -1
        for i in range(n):
            if not used[i] and dist[i] < d0:
                idx = i
                d0  = dist[i]
        if idx == -1:
            return dist
        else:
            used[idx] = 1
            for j in range(n):
                if not used[j] and dist[j] > dist[idx]+d[idx][j]:
                    dist[j] = dist[idx]+d[idx][j]
    return dist

from math import hypot
d = [[max(0.0,hypot((xi-xj),(yi-yj))-ri-rj) for xj,yj,rj in xyr] for xi,yi,ri in xyr]

#print(d)
dist = Dijkstra_matrix(d,n)
print((dist[-1]))
#print(dist)








import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


xs,ys,xt,yt = list(map(int, input().split()))
n = int(input())
xyr = [None]*(n+2)
for i in range(n):
    xyr[i] = tuple(map(int, input().split()))
from itertools import product
# ns = [[] for _ in range(n+2)]
data = []
rs = []
cs = []
s = n
t = n+1
xyr[s] = (xs,ys,0)
xyr[t] = (xt,yt,0)
for i,j in product(range(n+2), range(n+2)):
    if i<j:
        d = max(0, ((xyr[i][0]-xyr[j][0])**2 + (xyr[i][1]-xyr[j][1])**2)**0.5 - (xyr[i][2]+xyr[j][2]))
        data.append(d)
        rs.append(i)
        cs.append(j)
import scipy.sparse
m = scipy.sparse.csr_matrix((data, (rs, cs)), shape=(n+2, n+2))
ans = scipy.sparse.csgraph.dijkstra(m, indices=t, directed=False)
print(ans[s])

from math import sqrt
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path
def distance(x0, y0, x1, y1):
    return sqrt((x1-x0)**2 + (y1-y0)**2)

xs, ys, xt, yt, n, *XYR = map(int, open(0).read().split())
P = [(xs, ys, 0), (xt, yt, 0)] + list(zip(XYR[::3], XYR[1::3], XYR[2::3]))

edges = np.zeros((n+2, n+2))
for i in range(n+1):
    for j in range(i+1, n+2):
        dist = distance(P[i][0], P[i][1], P[j][0], P[j][1])
        dist = max(dist - P[i][2] - P[j][2], 0.0)
        edges[i, j] = edges[j, i] = dist

G = csgraph_from_dense(edges, null_value=-1)
print(shortest_path(G, indices=0)[1])

import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

xy=list(map(int,input().split()))
n=int(input())
xyr=[list(map(int,input().split())) for i in range(n)]

def dijkstra(s,e):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

################################
n,w = n,(n+2)*(n+1)//2 #n:頂点数　w:辺の数

edge = [[] for i in range(n+2)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(n):
    for j in range(i+1,n):
        x1,y1,r1=xyr[i]
        x2,y2,r2=xyr[j]
        dis=math.sqrt((x2-x1)**2+(y2-y1)**2)
        edge[i+1].append((max(0,dis-r1-r2),j+1))
        edge[j+1].append((max(0,dis-r1-r2),i+1))
for i in range(n):
    x1,y1,r1=xyr[i]
    dis=math.sqrt((xy[0]-x1)**2+(xy[1]-y1)**2)
    edge[0].append((max(0,dis-r1),i+1))
    edge[i+1].append((max(0,dis-r1),0))
    dis=math.sqrt((xy[2]-x1)**2+(xy[3]-y1)**2)
    edge[n+1].append((max(0,dis-r1),i+1))
    edge[i+1].append((max(0,dis-r1),n+1))
edge[0].append((math.sqrt((xy[0]-xy[2])**2+(xy[1]-xy[3])**2),n+1))
edge[n+1].append((math.sqrt((xy[0]-xy[2])**2+(xy[1]-xy[3])**2),0))
# print(edge)
n=n+2
print(dijkstra(0,edge)[-1])

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
xs, ys, xt, yt = map(int, input().split())
N = int(input())

x_list = []
y_list = []
r_list = []
x_list.append(xs)
y_list.append(ys)
r_list.append(0)
x_list.append(xt)
y_list.append(yt)
r_list.append(0)
for _ in range(N):
    x, y, r = map(int, input().split())
    x_list.append(x)
    y_list.append(y)
    r_list.append(r)

edges = [[] for _ in range(N+2)]
for i in range(N+1):
    for j in range(i+1, N+2):
        x1, y1, r1 = x_list[i], y_list[i], r_list[i]
        x2, y2, r2 = x_list[j], y_list[j], r_list[j]
        d = max(0, ((x1 - x2)**2 + (y1 - y2)**2)**0.5 - r1 - r2)
        edges[i].append((j, d))
        edges[j].append((i, d))
# print(edges)

INF = 10**10
dist = [INF] * (N+2)
hq = [(0, 0)] # (distance, node)
dist[0] = 0
while hq:
    cost, node = heappop(hq)
    if cost > dist[node]:
        continue
    for next, cost in edges[node]:
        if dist[node] + cost < dist[next]:
            dist[next] = dist[node] + cost
            heappush(hq, (dist[next], next))

# print(dist)
print(dist[1])

def resolve():
    import sys
    input = sys.stdin.readline

    import heapq
    def dijkstra_heap(s,g,edge):
        #始点sから各頂点への最短距離
        d = [10**20] * (n+2)
        used = [True] * (n+2) #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        sx,sy,sr=edge[s][0],edge[s][1],edge[s][2]
        for i in range(n+2):
            x,y,r=edge[i][0],edge[i][1],edge[i][2]
            dist=((x-sx)**2+(y-sy)**2)**(1/2)
            heapq.heappush(edgelist,(max(dist-r-sr,0),i))
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            v = minedge[1]
            if not used[v]:
                continue
            d[v] = minedge[0]
            used[v] = False
            bx,by,br=edge[v][0],edge[v][1],edge[v][2]
            for i in range(n+2):
                x,y,r=edge[i][0],edge[i][1],edge[i][2]
                dist=((x-bx)**2+(y-by)**2)**(1/2)
                if used[i]:
                    heapq.heappush(edgelist,(max(dist-r-br,0)+d[v],i))
            if not used[g]:
                break
        return d[g]

    sx,sy,gx,gy = map(int,input().split()) #n:頂点数　w:辺の数
    n=int(input())
    edge=[(sx,sy,0),(gx,gy,0)]
    for i in range(2,n+2):
        x,y,r=map(int,input().split())
        edge.append((x,y,r))
    print(dijkstra_heap(0,1,edge))

def __starting_point():
    resolve()
__starting_point()

from math import dist
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
from numpy import full, inf
from itertools import combinations

sx, sy, tx, ty, N, *XYR = map(int, open(0).read().split())

A = [(sx, sy, 0), (tx, ty, 0)] + list(zip(*[iter(XYR)] * 3))

D = full((N + 2, N + 2), inf)
for (i, (ax, ay, ad)), (j, (bx, by, bd)) in combinations(enumerate(A), 2):
    D[i][j] = max(
        0,
        dist((ax, ay), (bx, by)) - ad - bd
    )

print(dijkstra(csgraph_from_dense(D, null_value=inf), False, 0)[1])

from heapq import heappush,heappop
xs,ys,xt,yt = map(int,input().split())
n = int(input())
XY = [list(map(int,input().split())) for i in range(n)]
XY.append([xs,ys,0])
XY.append([xt,yt,0])

e = [[10**15]*(n+2) for i in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        xi,yi,ri = XY[i]
        xj,yj,rj = XY[j]
        dif = max(0.0,((xi-xj)**2+(yi-yj)**2)**0.5-ri-rj)
        e[i][j] = e[j][i] = dif

h = []
heappush(h,(0,n))
dis = [10**15]*(n+2)
dis[n] = 0
while h:
    cost,now = heappop(h)
    if cost > dis[now]:
        continue
    for nex,dif in enumerate(e[now]):
        if dis[nex] > dis[now]+dif:
            dis[nex] = dis[now]+dif
            heappush(h,(dis[nex],nex))
print(dis[-1])

from struct import pack, unpack
import math
from heapq import heapify, heappush as hpush, heappop as hpop
xs, ys, xt, yt = map(int, input().split())
N = int(input())
X = [(xs, ys, 0), (xt, yt, 0)]
for _ in range(N):
    x, y, r = map(int, input().split())
    X.append((x, y, r))

N += 2
DD = [[0] * N for _ in range(N)]
for i in range(N):
    xi, yi, ri = X[i]
    for j in range(N):
        xj, yj, rj = X[j]
        DD[i][j] = max(math.sqrt((xi-xj)**2 + (yi-yj)**2) - (ri+rj), 0)

def dijkstra(n, E, i0=0):
    D = [1 << 40] * n
    D[i0] = 0
    Q = set([i for i in range(n)])
    while Q:
        d = 1 << 40
        for q in Q:
            if D[q] < d:
                i = q
                d = D[q]
        Q.remove(i)
        for j, w in enumerate(DD[i]):
            if j == i: continue
            nd = d + w
            if D[j] > nd:
                D[j] = nd
    return D

print(dijkstra(N, X)[1])

a,b,c,d=map(int, input().split())
N=int(input())
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
R=[0]*(N+2)
A=[]
for i in range(N):
  x,y,r=map(int, input().split())
  A.append((x,y))
  R[i]=r
A.append((a,b))
A.append((c,d))
cost=[[float('inf') for i in range(N+2)] for i in range(N+2)]
for i in range(N+1):
  for j in range(i+1,N+2):
    d=(A[i][0]-A[j][0])**2+(A[i][1]-A[j][1])**2
    cost[i][j]=max(0,d**0.5-(R[i]+R[j]))
    cost[j][i]=max(0,d**0.5-(R[i]+R[j]))
D=dijkstra(N,N+2,(N+2)*(N+1)//2,cost)
print(D[N+1])

from heapq import heappush,heappop
xs,ys,xt,yt = map(int,input().split())
n = int(input())
XY = [list(map(int,input().split())) for i in range(n)]
XY.append([xs,ys,0])
XY.append([xt,yt,0])
inf = 10**14
e = [[inf]*(n+2) for i in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        xi,yi,ri = XY[i]
        xj,yj,rj = XY[j]
        dif = max(0,((xi-xj)**2+(yi-yj)**2)**0.5-ri-rj)
        e[i][j] = e[j][i] = dif

h = []
heappush(h,(0,n))
dis = [inf]*(n+2)
dis[n] = 0
while h:
    cost,now = heappop(h)
    if cost > dis[now]:
        continue
    for nex,dif in enumerate(e[now]):
        if dis[nex] > dis[now]+dif:
            dis[nex] = dis[now]+dif
            heappush(h,(dis[nex],nex))
print(dis[-1])

#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

#import math,heapq
from math import sqrt
from heapq import heappush,heappop

def pdist(x1,y1,x2,y2):
    return sqrt((x2-x1)**2+(y2-y1)**2)

xs,ys,xt,yt = inm()
n = inn()
cir = []
for i in range(n):
    x,y,r = inm()
    cir.append((x,y,r))
dst = [[0]*(n+2) for i in range(n+2)]
dst[n][n+1] = dst[n+1][n] = pdist(xs,ys,xt,yt)
for i in range(n):
    x,y,r = cir[i]
    dst[n][i] = dst[i][n] = max(0.0,pdist(xs,ys,x,y)-r)
    dst[n+1][i] = dst[i][n+1] = max(0.0,pdist(xt,yt,x,y)-r)
    for j in range(i+1,n):
        xx,yy,rr = cir[j]
        dst[j][i] = dst[i][j] = \
          max(0.0,pdist(xx,yy,x,y)-rr-r)

if False and DBG:
    for i in range(n+2):
        ddprint(dst[i])

cost = [float(BIG)]*(n+2)
q = [(0.0,n)]
while len(q)>0:
    d,p = heappop(q)
    #ddprint(f"{d=} {p=}")
    if cost[p]<=d:
        continue
    cost[p] = d
    for v in range(n+2):
        newdist = d+dst[p][v]
        if v!=p and newdist<cost[v]:
            heappush(q,(newdist, v))

print(cost[n+1])


from heapq import heapify,heappop,heappush
import sys
import math

input = sys.stdin.readline

xs, ys, xt, yt = list(map(int, input().split()))
N = int(input())

A = [(xs,ys,0)]
for i in range(N):
  A.append(tuple(map(int, input().split()))) # x, y, r = map(int, input().split())
A.append((xt,yt,0)) 

task = [[0.,0]]
heapify(task)
visited = set()
while task:
  #print(task)
  while task:
    c, p = heappop(task)
    if p not in visited:
      break
    if not task:
      print("error")
      return
  if p == N+1:
    print(c)
    return
     
  visited.add(p)
  xp, yp, rp = A[p] 
  
  for q in range(N+2):
    if q not in visited:
      xq, yq, rq = A[q]
      l = max(0.,math.sqrt((xq - xp)**2 + (yq - yp)**2)-rq-rp)
      heappush(task,[c+l, q])
  
  
    
    
      
  
  


from math import sqrt
import heapq

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    st = set()
    for i in range(n):
        st.add(i)
    dist = [float("inf")]*n
    dist[n-2] = 0
    dist[n-1] = calc(arr, n-2, n-1)
    hq = []
    heapq.heappush(hq, [0, n-2])
    while len(hq) > 0:
        _, p = heapq.heappop(hq)
        if p in st:
            st.remove(p)
            for nxt in st:
                d = calc(arr, p, nxt)
                if dist[nxt] > dist[p] + d:
                    dist[nxt] = dist[p] + d
                    heapq.heappush(hq, [dist[nxt], nxt])
    print(dist[-1])

def __starting_point():
    main()
__starting_point()

from heapq import *

sx, sy, tx, ty = list(map(int, input().split()))
N = int(input())
circles = [tuple(map(int, input().split())) for _ in range(N)]

s = N
t = N + 1
adj_matrix = [[0] * (N + 2) for _ in range(N + 2)]
adj_matrix[s][t] = adj_matrix[t][s] = ((tx-sx)**2 + (ty-sy)**2 )** 0.5 
for v, (x, y, r) in enumerate(circles):
    adj_matrix[s][v] = adj_matrix[v][s] = max(0, ((x-sx)**2 + (y-sy)**2) ** 0.5 - r)
    adj_matrix[t][v] = adj_matrix[v][t] = max(0, ((x-tx)**2 + (y-ty)**2)** 0.5 - r)
    
for v1, (x1, y1, r1) in enumerate(circles):
    for v2, (x2, y2, r2) in enumerate(circles[v1+1:], start=v1+1):
        adj_matrix[v1][v2] = adj_matrix[v2][v1] = max(0, ( ((x1-x2)**2 + (y1-y2)**2)**0.5 - r1 - r2))

dp = [float('inf')] * (N + 2)
dp[t] = 0
vis = [False] * (N + 2)
pq = [(0, t)]
while pq:
    cost, v = heappop(pq)
    if vis[v]:
        continue
    vis[v] = True
    for nv, dist in enumerate(adj_matrix[v]):
        if dp[nv] > cost + dist:
            dp[nv] = cost + dist
            heappush(pq, (dp[nv], nv))

# print(dp)
print((dp[s]))


def main():
    from math import hypot
    import sys
    input = sys.stdin.readline

    inf = 1 << 60

    xs, ys, xt, yt = list(map(int, input().split()))
    N = int(input())

    def dist(p1, p2):
        d = hypot(p1[0] - p2[0], p1[1] - p2[1])
        return max(0, d - (p1[2] + p2[2]))

    ps = [(xs, ys, 0)]
    ps += (tuple(map(int, input().split())) for _ in range(N))
    ps += [(xt, yt, 0)]

    adj = [[inf] * (N + 2) for _ in range(N + 2)]

    for i, p1 in enumerate(ps):
        for j, p2 in enumerate(ps):
            if i <= j: break  # 自己辺なし
            adj[i][j] = adj[j][i] = dist(p1, p2)

    def dijkstra(s):
        dist = [inf] * (N + 2)
        dist[s] = 0
        det = [0] * (N + 2)

        c, v = 0, s
        det[s] = 1
        while True:
            for u, dc in enumerate(adj[v]):
                nc = c + dc
                if dist[u] <= nc: continue
                dist[u] = nc

            c, v = -1, -1
            for u, d in enumerate(dist):
                if det[u]: continue
                if ~v and c <= d: continue
                c, v = d, u
            if not (~v): break
            det[v] = 1

        return dist

    print((dijkstra(s=0)[N + 1]))


def __starting_point():
    main()

__starting_point()

def main():
    import sys
    input = sys.stdin.readline

    INF = 10 ** 10

    from math import sqrt

    xs, ys, xg, yg = map(int, input().split())

    N = int(input())
    XYR = [tuple(map(int, input().split())) for _ in range(N)]

    G = [[] for _ in range(N + 2)]

    def diff1(i, j):
        tmp = (XYR[i][0] - XYR[j][0]) ** 2 + (XYR[i][1] - XYR[j][1]) ** 2
        R = XYR[i][2] + XYR[j][2]
        return max(0, sqrt(tmp) - R)

    for i in range(N - 1):
        for j in range(i + 1, N):
            tmp = diff1(i, j)
            G[i].append((tmp, j))
            G[j].append((tmp, i))

    def diff2(x, y, i):
        tmp = (x - XYR[i][0]) ** 2 + (y - XYR[i][1]) ** 2
        R = XYR[i][2]
        return max(0, sqrt(tmp) - R)

    for i in range(N):
        tmp = diff2(xs, ys, i)
        G[N].append((tmp, i))
        G[i].append((tmp, N))


    for i in range(N):
        tmp = diff2(xg, yg, i)
        G[N + 1].append((tmp, i))
        G[i].append((tmp, N + 1))

    tmp = (xs - xg) ** 2 + (ys - yg) ** 2
    G[N].append((sqrt(tmp), N + 1))
    G[N + 1].append((sqrt(tmp), N))

    d = [INF] * (N + 2) #頂点sからの距離

    def dijksrea(s): #始点s
        from heapq import heappop, heappush
        d[s] = 0 #始点の距離を0にする
        pque = []
        heappush(pque, (0, s)) #要素を[距離、頂点]として管理　最初の位置を入れる

        while pque: #queの中に要素が残っている時
            p = heappop(pque) #最も距離が短いものを取り出す
            v = p[1] #距離が最も短い頂点
            if d[v] < p[0]: #取り出した値より既に小さい値がdに入っているときは無視して次へ
                continue
            for i in range(len(G[v])): #頂点vの隣接リストを走査
                e = G[v][i]
                if d[e[1]] > d[v] + e[0]: #距離が更新できるかを検討
                    d[e[1]] = d[v] + e[0]
                    heappush(pque, (d[e[1]], e[1])) #更新できた場合、その値をpqueに入れる

    dijksrea(N)
    print (d[N + 1])

    # print (d)

def __starting_point():
    main()
__starting_point()

# Cosmic rays
import math
import heapq

xs, ys, xt, yt = list(map(int, input().split()))
N = int(input())

d = [((xs, ys), 0, 0)]
# node,radius

for _ in range(N):
    x, y, r = list(map(int, input().split()))
    d.append(((x, y), _+1, r))

graph = {i: [] for i in range(N+2)}

d.append(((xt, yt), N+1, 0))
for i in range(N+2):
    for j in range(i+1, N+2):
        p, point, rad = d[i]
        q, point2, rad2 = d[j]
        D = math.hypot(p[0]-q[0], p[1]-q[1])
        if D > (rad+rad2):
            graph[i].append((D-rad-rad2, j))
            graph[j].append((D-rad-rad2, i))
        else:
            graph[i].append((0, j))
            graph[j].append((0, i))


def dijkstra(s, graph):
    n = len(graph)
    dist = [float("inf") for i in range(n+1)]
    dist[s] = 0
    pq = []
    heapq.heapify(pq)
    heapq.heappush(pq, (0, s))
    while pq:
        mini_dis, node = heapq.heappop(pq)
        if dist[node] < mini_dis:
            continue
        for w, point in graph[node]:
            if dist[point] < w:
                continue
            newlen = dist[node]+w
            if newlen < dist[point]:
                heapq.heappush(pq, (newlen, point))
                dist[point] = newlen
    return dist

K=dijkstra(0,graph)[N+1]
print(K)


from heapq import heappop, heappush, heapify
from collections import deque

class Graph():  #non-directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def dijkstra(self, s, INF=10**18, restore_to=None):
        dist = [INF for _ in range(self.n)]
        dist[s] = 0
        heap = [(0, s)]
        prev = [None for _ in range(self.n)]
        while heap:
            cost, node = heappop(heap)
            if dist[node] < cost:
                continue
            for adj, adjcost in self.graph[node]:
                if dist[node] + adjcost < dist[adj]:
                    dist[adj] = dist[node] + adjcost
                    prev[adj] = node
                    heappush(heap, (dist[adj], adj))
        if restore_to is not None:
            g = restore_to
            if dist[g] == INF:
                return dist, False
            path = [g]
            node = g
            while node != s:
                node = prev[node]
                path.append(node)
            return dist, path[::-1]
        return dist

def dist(p, q):
    px, py = p
    qx, qy = q
    return ((px - qx)**2 + (py - qy)**2)**0.5

xs, ys, xt, yt = map(int, input().split())
s = (xs, ys)
t = (xt, yt)

N = int(input())

barrier = [tuple(map(int, input().split())) for _ in range(N)]
edge = []

edge.append((0, N + 1, dist(s, t)))

for i in range(N):
    xi, yi, ri = barrier[i]
    pi = (xi, yi)
    d = max(dist(s, pi) - ri, 0)
    edge.append((0, i + 1, d))

for i in range(N):
    xi, yi, ri = barrier[i]
    pi = (xi, yi)
    d = max(dist(t, pi) - ri, 0)
    edge.append((N + 1, i + 1, d))

for i in range(N - 1):
    for j in range(i + 1, N):
        xi, yi, ri = barrier[i]
        xj, yj, rj = barrier[j]
        pi = (xi, yi)
        pj = (xj, yj)
        d = max(dist(pi, pj) - ri - rj, 0)
        edge.append((i + 1, j + 1, d))

g = Graph(N + 2, edge, 0)

print(g.dijkstra(0)[N + 1])

from heapq import heappush,heappop
xs,ys,xt,yt = map(int,input().split())
n = int(input())
XY = [list(map(int,input().split())) for i in range(n)]
XY.append([xs,ys,0])
XY.append([xt,yt,0])

e = [[9999999999]*(n+2) for i in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        xi,yi,ri = XY[i]
        xj,yj,rj = XY[j]
        dif = max(0.0,((xi-xj)**2+(yi-yj)**2)**0.5-ri-rj)
        e[i][j] = e[j][i] = dif

h = []
heappush(h,(0,n))
dis = [float("INF")]*(n+2)
dis[n] = 0
while h:
    cost,now = heappop(h)
    if cost > dis[now]:
        continue
    for nex,dif in enumerate(e[now]):
        if dis[nex] > dis[now]+dif:
            dis[nex] = dis[now]+dif
            heappush(h,(dis[nex],nex))
print(dis[-1])

from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
xs,ys,xt,yt = map(int,input().split())
N=int(input())
xyr = [tuple(map(int,input().split())) for _ in range(N)]
xyr.append((xs,ys,0))
xyr.append((xt,yt,0))
b = [[-1]*(N+2) for _ in range(N+2)]
for i in range(N+2):
    x1, y1, r1 = xyr[i]
    for j in range(i+1,N+2):
        x2,y2,r2 = xyr[j]
        r = max(0, ((x1-x2)**2+(y1-y2)**2)**0.5-(r1+r2))
        b[i][j] = r
        b[j][i] = r
Graph = csgraph_from_dense(b, null_value=-1)
start = N
end = N+1
print(dijkstra(Graph, indices=start)[end])

import sys
import heapq
my_input = sys.stdin.readline

def main():
    xs, ys, xt, yt = list(map(int, my_input().split()))
    N = int(my_input())
    C = [(xs, ys, 0), (xt, yt, 0)]
    C += [tuple(map(int, my_input().split())) for i in range(N)]

    G = [[] for i in range(N+2)]
    for i in range(N + 2):
        for j in range(i + 1, N + 2):
            cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
            G[i].append((j, cost))
            G[j].append((i, cost))


    def dijkstra(graph, start, inf=float('inf')):
        import heapq
        n = len(graph)
        distances = [inf] * n
        distances[start] = 0
        visited = [False] * n

        # 距離・頂点
        hq = [(0, start)]
        while hq:
            dist, fr = heapq.heappop(hq)
            visited[fr] = True
            if distances[fr] < dist:
                continue
            if fr == 1:
                return distances


            for to, cost in graph[fr]:
                new_dist = distances[fr] + cost
                if (visited[to]) or (distances[to] <= new_dist):
                    continue

                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

        return distances


    dist = dijkstra(G, 0)
    print((dist[1]))


def __starting_point():
    main()

__starting_point()

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


xs,ys,xt,yt = list(map(int, input().split()))
n = int(input())
xyr = [None]*(n+2)
for i in range(n):
    xyr[i] = tuple(map(int, input().split()))
from itertools import product
ns = [[] for _ in range(n+2)]
s = n
t = n+1
xyr[s] = (xs,ys,0)
xyr[t] = (xt,yt,0)
for i,j in product(list(range(n+2)), list(range(n+2))):
    if i<j:
        d = max(0, ((xyr[i][0]-xyr[j][0])**2 + (xyr[i][1]-xyr[j][1])**2)**0.5 - (xyr[i][2]+xyr[j][2]))
        ns[i].append((d,j))
        ns[j].append((d,i))
def dijkstra(start):
    import heapq
    vals = [None] * (n+2)
    h = [(0, start)] # (距離, ノード番号)
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        if u==t:
            break
        if val>vals[u]:
          continue
        for d, v in ns[u]:
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
vals = dijkstra(s)
ans = vals[t]
print(ans)


import sys
input = sys.stdin.readline
import heapq

def dijkstra(n, s, edges):
    hq = [(0, s)]
    cost = [float('inf')] * n
    cost[s] = 0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]:
            continue
        for d, u in edges[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost[-1]

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    circles = []
    circles.append([xs, ys, 0])
    for _ in range(n):
        circles.append(list(map(int, input().split())))
    circles.append([xt, yt, 0])
    edges = [[] for _ in range(n + 2)]
    for i in range(n + 2):
        for j in range(i + 1, n + 2):
            dx = circles[i][0] - circles[j][0]
            dy = circles[i][1] - circles[j][1]
            d = (dx ** 2 + dy ** 2) ** 0.5
            r = circles[i][2] + circles[j][2]
            edges[i].append([max(0, d - r), j])
            edges[j].append([max(0, d - r), i])

    ans = dijkstra(n + 2, 0, edges)
    print(ans)
    
main()

xs,ys,xt,yt=list(map(int,input().split()))
N=int(input())
XY=[tuple(map(int,input().split())) for i in range(N)]
D=[[0]*(N+2) for i in range(N+2)]
XY.append((xs,ys,0))
XY.append((xt,yt,0))


for i in range(N+1):
  x1,y1,r1=XY[i]
  for j in range(i+1,N+2):
    x2,y2,r2=XY[j]
    d = (x1-x2)**2 + (y1-y2)**2
    d = d **(0.5)
    D[i][j] = max(0,d-r1-r2)
    D[j][i]=D[i][j]
import heapq
hq=[]
hq.append((0,N))
s=set([i for i in range(N+2)])

while(hq):
  
  c,x=heapq.heappop(hq)
  if x==N+1:
    print(c)
    return
  if x in s:
    
    s.remove(x)
  else:
    continue
  for i in s:
    heapq.heappush(hq,(c+D[x][i],i))
  
  


from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

xs, ys, xt, yt = map(int, input().split())
N = int(input())
xyr = [list(map(int, input().split())) for i in range(N)]

def dist(x1, y1, x2, y2):
  return ((x1-x2)**2 + (y1-y2)**2)**0.5

row = [0]
col = [1]
data = [dist(xs, ys, xt, yt)]
for i, (xi, yi, ri) in enumerate(xyr, 2):
  d1 = max(0, dist(xi, yi, xs, ys) - ri)
  d2 = max(0, dist(xi, yi, xt, yt) - ri)
  row.extend([0, 1])
  col.extend([i, i])
  data.extend([d1, d2])
  for j in range(i-1, N):
    xj, yj, rj = xyr[j]
    dij = max(0, dist(xi, yi, xj, yj) - ri - rj)
    row.append(i)
    col.append(j+2)
    data.append(dij)

graph = csr_matrix((data, (row, col)), shape=(N+2, N+2))
dist = dijkstra(graph, directed=False, indices=0)
print(dist[1])

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    x_s, y_s, x_t, y_t = list(map(int, readline().split()))
    A = np.array([[x_s, y_s, 0],
                  [x_t, y_t, 0]], dtype=np.int)
    
    N = int(readline())
    B = np.array(read().split(), dtype=np.int).reshape(-1, 3)
    XY, R = np.hsplit(np.concatenate((A, B)), [2])
    
    d = np.expand_dims(XY, axis=1) - np.expand_dims(XY, axis=0)
    d = np.sqrt(np.sum(np.square(d), axis=-1))
    d -= R + R.reshape(1, -1)
    d = np.maximum(d, 0)
    np.fill_diagonal(d, -1)
    d = csgraph_from_dense(d, null_value=-1)
     
    ans = dijkstra(d, indices=0)[1]
    print(ans)


def __starting_point():
    main()

__starting_point()

xs,yx,xt,yt = map(int,input().split())
N = int(input())
l = [[],[xs,yx,0],[xt,yt,0]]
for i in range(N):
  l.append(list(map(int,input().split())))
##距離リスト
d = [[0]*(N+3) for _ in range(N+3)]
for i in range(1,N+3):
  d[i][i] = 0
#O(10**6)
for i in range(1,N+3):
  for j in range(i+1,N+3):
    sa = (l[i][0]-l[j][0])**2 + (l[i][1]-l[j][1])**2
    kyori = max(0,sa**(1/2)-l[i][2]-l[j][2])
    d[i][j] = kyori
    d[j][i] = kyori

md = [float("inf")]*(N+3)
h = [i for i in range(1,N+3)]
for i in range(1,N+3):
  md[i]=d[1][i]
seen = [False]*(N+3)
seen[1] = True
while True:
  #vを出す
  v = -1
  for i in h:
    if seen[i] == False and v == -1:
      v = i
    elif seen[i] == False and md[i] < md[v]:
      v = i
  if v == -1:
    break
  seen[v] = True
  for j in range(1,N+3):
    md[j] = min(md[j],md[v]+d[v][j])
print(md[2])      

from heapq import heappush,heappop
xs,ys,xt,yt = map(int,input().split())
n = int(input())
XY = [list(map(int,input().split())) for i in range(n)]
XY.append([xs,ys,0])
XY.append([xt,yt,0])
inf = 10**14
e = [[inf]*(n+2) for i in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        xi,yi,ri = XY[i]
        xj,yj,rj = XY[j]
        dif = max(0.0,((xi-xj)**2+(yi-yj)**2)**0.5-ri-rj)
        e[i][j] = e[j][i] = dif

h = []
heappush(h,(0,n))
dis = [inf]*(n+2)
dis[n] = 0
while h:
    cost,now = heappop(h)
    if cost > dis[now]:
        continue
    for nex,dif in enumerate(e[now]):
        if dis[nex] > dis[now]+dif:
            dis[nex] = dis[now]+dif
            heappush(h,(dis[nex],nex))
print(dis[-1])

import heapq

xs, ys, xt, yt = list(map(int, input().split()))
N = int(input())
XYR = [list(map(int, input().split())) for i in range(N)]
XYR.append([xs, ys, 0])
XYR.append([xt, yt, 0])
L = [[9999999999]*(N+2) for i in range(N+2)]
for i in range(N+2):
    for j in range(i, N+2):
        x1, y1, r1 = XYR[i]
        x2, y2, r2 = XYR[j]
        L[i][j] = L[j][i] = max(((x1-x2)**2+(y1-y2)**2)**0.5-r1-r2, 0.0)


# 計算量 O((E+V)logV)
num = N+2  # グラフのノード数
start = num-2

distance = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する
distance[start] = 0
q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
heapq.heappush(q, (0, start))  # 始点をpush

while len(q) != 0:
    prov_cost, src = heapq.heappop(q)  # pop

    # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
    if distance[src] < prov_cost:
        continue

    # 他の頂点の探索
    for destination, cost in enumerate(L[src]):
        if distance[destination] > distance[src] + cost:
            distance[destination] = distance[src] + cost  # distの更新
            heapq.heappush(q, (distance[destination], destination))  # キューに新たな仮の距離の情報をpush
            prev[destination] = src  # 前の頂点を記録

print((distance[-1]))


from heapq import heapify, heappop, heappush
xs,ys,xt,yt = map(int,input().split()); INF = float("inf")
N = int(input())
Z = []
for i in range(N):
  x,y,r = map(int,input().split())
  Z.append((x,y,r,i)) #x,y,r,ID
G = [[] for _ in range(N+2)]
for i in range(N):
  dis = ((Z[i][0]-xs)**2 + (Z[i][1]-ys)**2)**0.5
  dis -= Z[i][2]
  dis = max(0,dis)
  G[0].append((dis,i+1))
dis = ((xt-xs)**2 + (yt-ys)**2)**0.5
G[0].append((dis,N+1))
              
for i in range(N):
  for j in range(N):
    if i == j:
      continue
    dis = ((Z[i][0]-Z[j][0])**2 + (Z[i][1]-Z[j][1])**2)**0.5
    dis -= Z[i][2]+Z[j][2]
    dis = max(0,dis)
    G[i+1].append((dis,j+1)) #1index
  dis = ((Z[i][0]-xt)**2 + (Z[i][1]-yt)**2)**0.5
  dis -= Z[i][2]
  dis = max(0,dis)
  G[i+1].append((dis,N+1))
#print(G)

def dijkstra_heap2(s,G):
  #S:start, V: node, E: Edge, G: Graph
  V = len(G)
  d = [INF for _ in range(V)]
  d[s] = 0
  PQ = []
  heappush(PQ,(0,s))
  
  while PQ:
    c,v = heappop(PQ)
    if d[v] < c:
      continue
    d[v] = c
    for cost,u in G[v]:
      if d[u] <= cost + d[v]:
        continue
      d[u] = cost + d[v]
      heappush(PQ,(d[u], u))
  
  return d

ret = dijkstra_heap2(0,G)
#print(ret)
ans = ret[N+1]
print(ans)

import heapq
from math import sqrt
def dijkstra(s, n, g): # s: start, n: |V|, g; glaph 
    INF = 10**18
    d = [INF] * n
    #-- record the prev vertex of each one for restoring the route --
    # prev_vl = [-1]*n 
    d[s] = 0
    que = [] # (a,b): a... shortest dist, b... v
    heapq.heappush(que, (0, s))

    while que:
        dist, v = heapq.heappop(que)
        if d[v] < dist: continue # if v has been already used -> continue
        for next_v, cost in g[v]:
            if d[next_v] > d[v] + cost:
                d[next_v] = d[v] + cost
                # prev_vl[next_v] = v
                heapq.heappush(que, (d[next_v], next_v))

    return d



xs,ys,xg,yg = map(int, input().split())
xyrl = []
xyrl.append((xs,ys,0))
xyrl.append((xg,yg,0))
n = int(input())
for _ in range(n):
    x,y,r = map(int, input().split())
    xyrl.append((x,y,r))

g = [[] for _ in range(n+2)]
for i in range(n+2):
    for j in range(n+2):
        if i == j: continue
        x1,y1,r1 = xyrl[i]
        x2,y2,r2 = xyrl[j]
        d = sqrt( (x2-x1)**2 + (y2-y1)**2 )-r1-r2
        if d < 0: d = 0
        g[i].append((j,d))

dists = dijkstra(0,n+2,g)
print(dists[1])

from struct import pack, unpack
import math
from heapq import heapify, heappush as hpush, heappop as hpop
class FibonacciHeap():
    def __init__(self, mm):
        self.inf = 1 << 100
        self.mm = mm
        self.roots = [[] for _ in range(mm)]
        self.min = self.inf
        self.minroot = None
    
    def add(self, v):
        nd = self.node(v)
        self.add_node(nd)
        return nd
    
    def add_node(self, nd):
        k = nd.order
        if nd.value < self.min:
            self.min = nd.value
            self.minroot = nd
        self.roots[k].append(nd)
    
    def setmin(self):
        mi = self.inf
        mirt = None
        for i, rt in enumerate(self.roots):
            while len(rt) >= 2:
                nd1 = rt.pop()
                nd2 = rt.pop()
                self.roots[i+1].append(nd1.meld(nd2))
            if len(rt) and rt[0].value < mi:
                mi = rt[0].value
                mirt = rt[0]
        self.min = mi
        self.minroot = mirt
        return self.minroot
    
    def pop(self):
        nd = self.minroot
        mi = nd.value
        self.roots[nd.order].remove(nd)
        ch = nd.repChild
        if ch:
            nd = ch.right
            while 1:
                nnd = nd.right
                self.add_node(nd)
                l = nd.left
                r = nd.right
                if r != nd:
                    nd.right = nd
                    nd.left = nd
                    l.right = r
                    r.left = l
                nd.parent = None
                if nd == ch:
                    break
                nd = nnd
        self.setmin()
        return mi
    class node():
        def __init__(self, value):
            self.parent = None
            self.left = self
            self.right = self
            self.repChild = None
            self.order = 0
            self.marked = 0
            self.value = value
        
        def meld(self, other):
            if self.value > other.value:
                return other.meld(self)
            other.parent = self
            if not self.repChild:
                self.repChild = other
            else:
                l = self.repChild
                r = l.right
                l.right = other
                r.left = other
                other.left = l
                other.right = r
            self.order += 1
            return self
    
    def movetop(self, nd):
        p = nd.parent
        nd.marked = 0
        if not p: return nd
        l = nd.left
        r = nd.right
        if r != nd:
            p.repChild = r
            nd.right = nd
            nd.left = nd
            l.right = r
            r.left = l
        else:
            p.repChild = None
        nd.parent = None
        self.add_node(nd)
        if not p.parent:
            self.roots[p.order].remove(p)
            p.order -= 1
            self.add_node(p)
        
    def prioritize(self, nd, v):
        p = nd.parent
        nd.value = v
        if v < self.min:
            self.min = v
            self.minroot = nd
        if not p or p.value <= v:
            return nd
        self.movetop(nd)
        nn = p
        while nn.parent:
            if nn.marked == 0:
                nn.marked = 1
                break
            else:
                p = nn.parent
                self.movetop(nn)
                nn = p
        return nd
            
    def debug(self):
        def _debug(nd):
            if not nd: return ""
            s = str(nd.value) + ("(" + str(nd.left.value) + "-" + str(nd.right.value) + ")" if nd != nd.right else "")
            if nd.repChild: s += "[C=" + str(nd.repChild.value) + "]"
            if nd.parent: s += "[P=" + str(nd.parent.value) + "]"
            if not nd.repChild: return s
            ss = []
            ch = nd.repChild
            idch = id(ch)
            nd = ch.right
            while 1:
                ss.append(_debug(nd))
                if id(nd) == idch: break
                nd = nd.right
            s += "[" + ", ".join(map(str, ss)) + "]"
            return s
        RE = []
        for i, root in enumerate(self.roots):
            for nd in root:
                if nd: RE.append("<" + str(i) + ">" + _debug(nd))
        s = "min=" + str(self.min) + " "
        print((s + " - ".join(map(str, RE))))
        
xs, ys, xt, yt = list(map(int, input().split()))
N = int(input())
X = [(xs, ys, 0), (xt, yt, 0)]
for _ in range(N):
    x, y, r = list(map(int, input().split()))
    X.append((x, y, r))

N += 2
DD = [[0] * N for _ in range(N)]
for i in range(N):
    xi, yi, ri = X[i]
    for j in range(N):
        xj, yj, rj = X[j]
        DD[i][j] = max(math.sqrt((xi-xj)**2 + (yi-yj)**2) - (ri+rj), 0)

m = 1023
def dijkstra(n, E, i0=0):
    fb = FibonacciHeap(100)
    inf = unpack("q", pack("d", 10 ** 10 / 1))[0]
    D = [10 ** 10 / 1] * n
    done = [0] * n
    D[i0] = 0
    V = []
    for i in range(n):
        v = (unpack("q", pack("d", (0.0 if i == i0 else 10 ** 10 / 1)))[0] | m) - (m - i)
        V.append(fb.add(v))
    while fb.minroot:
        di = fb.pop()
        d, i = unpack("d", pack("q", (di | m) - m))[0], di & m
        done[i] = 1
        for j, w in enumerate(DD[i]):
            if done[j] or j == i: continue
            nd = d + w
            if D[j] > nd:
                v = (unpack("q", pack("d", nd))[0] | m) - (m - j)
                fb.prioritize(V[j], v)
                D[j] = nd
    return D

print((dijkstra(N, X)[1]))






sx,sy,gx,gy = list(map(int,input().split()))
N = int(input())
zone = [list(map(int,input().split())) for i in range(N)]

zone = [[sx,sy,0]] + zone + [[gx,gy,0]]

G = [[0] * (N + 2) for i in range(N + 2)]
for i in range(len(zone) - 1):
  for j in range(i + 1, len(zone)):
    dist = ((zone[i][0] - zone[j][0]) ** 2 + (zone[i][1] - zone[j][1]) ** 2) ** 0.5
    dist = max(0, dist - (zone[i][2] + zone[j][2]))
    G[i][j] = dist
    G[j][i] = dist

import heapq as hq
# 浴びた距離, 頂点
q = [(0, 0)]
hq.heapify(q)
seen = set()
while q:
  dist, v = hq.heappop(q)
  if v in seen:
    continue
  seen.add(v)
  if v == N + 1:
    print(dist)
    break
  for i in range(len(G[v])):
    if i in seen:
      continue
    hq.heappush(q, (dist + G[v][i], i))


xs,ys,xe,ye=list(map(int,input().split()))
n=int(input())
xyr=[tuple(map(int,input().split())) for _ in range(n)]
xyr.append((xs,ys,0))
xyr.append((xe,ye,0))
d=[[0]*(n+2) for _ in range(n+2)]
for i in range(n+1):
  for j in range(i+1,n+2):
    x,y,r=xyr[i]
    nx,ny,nr=xyr[j]
    tmp=((x-nx)**2+(y-ny)**2)**0.5
    tmp-=r+nr
    tmp=max(tmp,0)
    d[i][j]=tmp
    d[j][i]=tmp



inf=float('inf')
seen=[inf]*(n+2)
seen[-2]=0
mi=set(range(n+2))
# n->n+1
while mi:
  min_idx=0
  min_d=inf
  for v in mi:
    if min_d>seen[v]:
      min_d=seen[v]
      min_idx=v
  v=min_idx
  mi.discard(v)
  if v==n+1:break
  for nv in mi:
    seen[nv]=min(seen[nv],seen[v]+d[v][nv])
print((seen[-1]))



import heapq

xs, ys, xt, yt = list(map(int, input().split()))
N = int(input())
XYR = [(xs, ys, 0), (xt, yt, 0)]
for _ in range(N):
  XYR.append(tuple(map(int, input().split())))

D = [[0]*(N+2) for _ in range(N+2)]
for i, (xi, yi, ri) in enumerate(XYR):
  for j, (xj, yj, rj) in enumerate(XYR[:i]):
    dx = xj - xi
    dy = yj - yi
    d = (dx*dx+dy*dy)**0.5
    D[i][j] = D[j][i] = max(0, d-ri-rj)

Q = [(0, 0)]
dist = [-1]*(N+2)
nvisited = 0
while nvisited<N+2:
  d, n = heapq.heappop(Q)
  if dist[n] != -1: continue
  dist[n] = d
  nvisited += 1

  for e, d_ne in enumerate(D[n]):
    if dist[e] == -1:
      heapq.heappush(Q, (d+d_ne, e))

print((dist[1]))


from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

sx,sy,gx,gy=map(int,input().split())
n=int(input())
arr=[[sx,sy,0]]+[list(map(int,input().split())) for _ in range(n)]+[[gx,gy,0]]
g=[[-1]*(n+2) for _ in range(n+2)]
for i in range(n+2):
  x1,y1,r1=arr[i]
  for j in range(n+2):
    x2,y2,r2=arr[j]
    g[i][j]=max(0.0,((x1-x2)**2+(y1-y2)**2)**0.5-(r1+r2))
g=csgraph_from_dense(g,null_value=-1)
ans=((sx-gx)**2+(sy-gy)**2)**0.5
print(min(ans,dijkstra(g,indices=0)[n+1]))

xs,ys,xt,yt = list(map(int,input().split()))
n = int(input())

v = [(xs,ys,0),(xt,yt,0)]
for i in range(n):
    x,y,r = list(map(int,input().split()))
    v.append((x,y,r))
path = [[] for i in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        l = max(0, ((v[i][0] - v[j][0])**2 + (v[i][1] - v[j][1])**2)**0.5 - v[i][2] - v[j][2])
        path[i].append((j,l))
        path[j].append((i,l))

import heapq
def Dijkstra(edge,start,v):
    d = [float('inf')]*v
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        if dist > d[p]:continue
        for to,cost in edge[p]:
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

d = Dijkstra(path, 0, n+2)
print((d[1]))


import sys
input = sys.stdin.readline
import heapq

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    
    def dijkstra(s):
        hq = [(0, s)]
        cost = [float('inf')] * (n + 2)
        cost[s] = 0
        while hq:
            c, v = heapq.heappop(hq)
            if c > cost[v]:
                continue
            for d, u in edges[v]:
                tmp = d + cost[v]
                if tmp < cost[u]:
                    cost[u] = tmp
                    heapq.heappush(hq, (tmp, u))
        return cost[-1]
    
    circles = []
    circles.append([xs, ys, 0])
    for _ in range(n):
        circles.append(list(map(int, input().split())))
    circles.append([xt, yt, 0])
    edges = [[] for _ in range(n + 2)]
    for i in range(n + 2):
        for j in range(i + 1, n + 2):
            dx = circles[i][0] - circles[j][0]
            dy = circles[i][1] - circles[j][1]
            d = (dx ** 2 + dy ** 2) ** 0.5
            r = circles[i][2] + circles[j][2]
            edges[i].append([max(0, d - r), j])
            edges[j].append([max(0, d - r), i])

    ans = dijkstra(0)
    print(ans)
    
main()

from collections import defaultdict as dd
from heapq import heappop, heappush
import math
xs, ys, xt, yt = list(map(int, input().split()))
N = int(input())
Cs = [list(map(int, input().split())) for _ in range(N)]
Cs.append([xs, ys, 0])
Cs.append([xt, yt, 0])

Es = dd(dict)
for i in range(N+2):
    xi, yi, ri = Cs[i]
    for j in range(i+1, N+2):
        xj, yj, rj = Cs[j]
        Es[i][j] = Es[j][i] = max(0, math.sqrt((xi-xj)**2 + (yi-yj)**2) - ri - rj)

# dists: sortest path
INF = float('inf')
dists = [INF] * (N+2)
dists[N] = 0

# dijk
q = []
close = set()
start = N
heappush(q, (0, start))
while q:
    d, node = heappop(q)
    if dists[node] < d:
        continue
    close.add(node)
    for to, c in list(Es[node].items()):
        if to in close or dists[to] <= d + c:
            continue
        dists[to] = d + c
        heappush(q, (dists[to], to))
print((dists[N+1]))


import heapq
def dijkstra_heap(N,s,edge):
    d = [float("inf")] * N #始点sから各頂点への最短距離
    used = [False] * N
    d[s] = 0
    used[s] = True
    edgelist = []
    #edgelist : [sからの暫定(未確定)最短距離,頂点]のリスト
    #edge[s] : sから出る枝の[重み,終点]のリスト
    for v,w in enumerate(edge[s]):
        heapq.heappush(edgelist,(w,v)) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    while len(edgelist):
        #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
        minedge = heapq.heappop(edgelist)
        #minedge : [sからの(確定)最短距離,頂点]
        v = minedge[1]
        if used[v]:
            continue
        d[v] = minedge[0]
        used[v] = True
        for u,w in enumerate(edge[v]):
            if not used[u]:
                heapq.heappush(edgelist,(d[v]+w,u))
    return d


################################
A, B, C, D = map(int, input().split())
N = int(input())

d = [[0]*(N+2) for _ in range(N+2)]

X = [0]*N
Y = [0]*N
R = [0]*N
for i in range(N):
    X[i],Y[i],R[i] = map(int, input().split())
d[0][-1] = ((C-A)**2+(D-B)**2)**0.5
d[-1][0] = ((C-A)**2+(D-B)**2)**0.5
for i in range(1,N+1):
    d_s = max(0,((X[i-1]-A)**2+(Y[i-1]-B)**2)**0.5-R[i-1])
    d_e = max(0,((X[i-1]-C)**2+(Y[i-1]-D)**2)**0.5-R[i-1])
    d[0][i],d[i][0] = d_s,d_s
    d[N+1][i],d[i][N+1] = d_e,d_e
    for j in range(1,N+1):
        d[i][j] = max(((X[i-1]-X[j-1])**2+(Y[i-1]-Y[j-1])**2)**0.5-R[i-1]-R[j-1],0)
s = 0 #始点
d = dijkstra_heap(N+2,s,d)
print(d[-1])

from heapq import *

sx, sy, tx, ty = list(map(int, input().split()))
N = int(input())
circles = [tuple(map(int, input().split())) for _ in range(N)]

s = N
t = N + 1
adj_matrix = [[0] * (N + 2) for _ in range(N + 2)]
adj_matrix[s][t] = adj_matrix[t][s] = ((tx-sx)**2 + (ty-sy)**2 )** 0.5 
for v, (x, y, r) in enumerate(circles):
    adj_matrix[s][v] = adj_matrix[v][s] = max(0, ((x-sx)**2 + (y-sy)**2) ** 0.5 - r)
    adj_matrix[t][v] = adj_matrix[v][t] = max(0, ((x-tx)**2 + (y-ty)**2)** 0.5 - r)
    
for v1, (x1, y1, r1) in enumerate(circles):
    for v2, (x2, y2, r2) in enumerate(circles[v1+1:], start=v1+1):
        adj_matrix[v1][v2] = adj_matrix[v2][v1] = max(0, ( ((x1-x2)**2 + (y1-y2)**2)**0.5 - r1 - r2))

dp = [float('inf')] * (N + 2)
dp[t] = 0
pq = [(0, t)]
while pq:
    cost, v = heappop(pq)
    if dp[v] < cost:
        continue
    for nv, dist in enumerate(adj_matrix[v]):
        if dp[nv] > cost + dist:
            dp[nv] = cost + dist
            heappush(pq, (dp[nv], nv))

# print(dp)
print((dp[s]))


xs, ys, xt, yt = map(int,input().split())
N = int(input())
L = [[xs, ys, 0], [xt, yt, 0]]

for _ in range(N):
    L.append(list(map(int,input().split())))

V = N + 2
G = [[] for _ in range(N+2)]
s = 0

for i in range(N+2):
    for j in range(N+2):
        if i != j:
            G[i].append([j, max(0, ((L[i][0] - L[j][0]) ** 2 + (L[i][1] - L[j][1]) ** 2) ** 0.5 - (L[i][2] + L[j][2]))])


INF = float('inf')

import heapq

def dijkstra(s):
    d = [INF for _ in range(V)]
    d[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    
    while len(que) != 0:
        p = heapq.heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e[0]] > d[v] + e[1]:
                d[e[0]] = d[v] + e[1]
                heapq.heappush(que, (d[e[0]], e[0]))

    return d

d = dijkstra(0)
print(d[1])

from heapq import heappush,heappop
xs,ys,xt,yt = map(int,input().split())
n = int(input())
XY = [list(map(int,input().split())) for i in range(n)]
XY.append([xs,ys,0])
XY.append([xt,yt,0])

e = [[9999999999]*(n+2) for i in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        xi,yi,ri = XY[i]
        xj,yj,rj = XY[j]
        dif = max(0.0,((xi-xj)**2+(yi-yj)**2)**0.5-ri-rj)
        e[i][j] = e[j][i] = dif

h = []
heappush(h,(0,n))
dis = [10**15]*(n+2)
dis[n] = 0
while h:
    cost,now = heappop(h)
    if cost > dis[now]:
        continue
    for nex,dif in enumerate(e[now]):
        if dis[nex] > dis[now]+dif:
            dis[nex] = dis[now]+dif
            heappush(h,(dis[nex],nex))
print(dis[-1])

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=list(map(int,input().split()))
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print((seen[n+1]))
def __starting_point():
  main()

__starting_point()

import typing
import sys
import math
import collections
import bisect
import itertools
import heapq
import decimal
import copy
import operator

# sys.setrecursionlimit(10000001)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

# buffer.readline()はこどふぉで死ぬ


def ni(): return int(sys.stdin.readline())
def ns(): return list(map(int, sys.stdin.readline().split()))
def na(): return list(map(int, sys.stdin.readline().split()))
def na1(): return list([int(x)-1 for x in sys.stdin.readline().split()])


# ===CODE===

def dist(l1, l2):
    return max(0, math.sqrt((l1[0]-l2[0])**2+(l1[1]-l2[1])**2)-l1[2]-l2[2])


def main():
    xs, ys, xt, yt = ns()
    n = ni()
    pos = [na() for _ in range(n)]
    pos.insert(0, [xs, ys, 0])
    pos.append([xt, yt, 0])
    d = [[dist(pos[i], pos[j]) for i in range(n+2)] for j in range(n+2)]

    mind = [INF for _ in range(n+2)]
    visited = [False for _ in range(n+2)]

    hq = []
    heapq.heappush(hq, (0, 0))
    # dist,idx
    mind[0] = 0
    while hq:
        dis, idx = heapq.heappop(hq)
        if visited[idx]:
            continue
        visited[idx]=True
        
        if idx==n+1:
            break
        for i in range(n+2):
            if i == idx:
                continue
            ndist = dis+d[idx][i]
            if ndist < mind[i] and ndist < mind[n+1]:
                mind[i] = ndist
                heapq.heappush(hq, (ndist, i))

    print((mind[n+1]))


def __starting_point():
    main()

__starting_point()

import sys
from heapq import heappop,heappush
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))


xs,ys,xt,yt = MI()
N = I()
XYR = []
for _ in range(N):
    XYR.append(tuple(MI()))
XYR.append((xs,ys,0))  # 始点を半径0のバリアとみなす
XYR.append((xt,yt,0))  # 終点を半径0のバリアとみなす

Graph = [[0]*(N+2) for _ in range(N+2)]  # Graph[i][j] = バリア i からバリア j までの'距離'
for i in range(N+1):
    x0,y0,r0 = XYR[i]
    for j in range(i+1,N+2):
        x1,y1,r1 = XYR[j]
        Graph[i][j] = max(0,((x1-x0)**2+(y1-y0)**2)**.5-r0-r1)
        Graph[j][i] = max(0,((x1-x0)**2+(y1-y0)**2)**.5-r0-r1)

# ダイクストラ法

dist = [10**10]*(N+2)  # dist[i] = バリア N からバリア i への最短'距離'
dist[N] = 0
q = []
heappush(q,(0,N))
flag = [0]*(N+2)
while q:
    d,i = heappop(q)
    if flag[i] == 1:
        continue
    flag[i] = 1

    for j in range(N+2):
        if flag[j] == 0:
            new_d = d+Graph[i][j]
            if new_d < dist[j]:
                dist[j] = new_d
                heappush(q,(new_d,j))

print((dist[N+1]))


inf=10**18
def D(a,b,c,d):
	return ((c-a)**2+(d-b)**2)**0.5
xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[(xs,ys,0)]
for i in range(n):
	xyr.append(tuple(map(int,input().split())))
xyr.append((xt,yt,0))
dis=[[inf]*(n+2) for i in range(n+2)]
for i in range(n+2):
	dis[i][i]=0
for i in range(n+2):
	for j in range(i):
		a,b,r1=xyr[i]
		c,d,r2=xyr[j]
		r=D(a,b,c,d)-(r1+r2)
		r=max(0,r)
		dis[i][j]=r
		dis[j][i]=r
cost=[inf]*(n+2)
cost[0]=0
visited=[0]*(n+2)
now=0
for i in range(n+2):
	visited[now]=1
	MIN=inf
	pre_now=-1
	for j in range(n+2):
		if visited[j]==0:
			cost[j]=min(cost[now]+dis[now][j],cost[j])
			if MIN>cost[j]:
				MIN=cost[j]
				pre_now=j
	now=pre_now			
print(cost[n+1])

from heapq import *

def dijkstra(graph, initial):
    ''' Dijkstra's shortest path algorithm. '''
    visited = {initial: 0}
    h, path = [(0, initial)], {}
    nodes = set(graph.keys())

    while nodes and h:
        current_weight, min_node = heappop(h)
        while h and (min_node not in nodes):
            current_weight, min_node = heappop(h)
        if not h and (min_node not in nodes):
            break

        nodes.remove(min_node)
        for v, w in graph[min_node]:
            weight = w + current_weight # weight update step
            if v not in visited or weight < visited[v]:
                visited[v] = weight
                heappush(h, (weight, v))
                path[v] = min_node
    return visited, path

xstart, ystart, xtarget, ytarget = map(int, input().split())
N = int(input())
circs = [tuple(map(int, input().split())) for _ in range(N)]

graph = {i: [] for i in range(N+2)}

from math import sqrt

for i in range(N):
  xi, yi, ri = circs[i]
  for j in range(i):
    xj, yj, rj = circs[j]
    d = max(sqrt((xi-xj)**2 + (yi-yj)**2) - ri - rj, 0)
    graph[i].append((j, d))
    graph[j].append((i, d))
  
  # start
  dst = max(sqrt((xi-xstart)**2 + (yi-ystart)**2) - ri, 0)
  graph[i].append((N, dst))
  graph[N].append((i, dst))
  
  dtgt = max(sqrt((xi-xtarget)**2 + (yi-ytarget)**2) - ri, 0)
  graph[i].append((N+1, dtgt))
  graph[N+1].append((i, dtgt))

dsrctgt = sqrt((xstart-xtarget)**2 + (ystart-ytarget)**2)
graph[N].append((N+1, dsrctgt))
graph[N+1].append((N, dsrctgt))
  
visited, _ = dijkstra(graph, N)
print(visited[N+1])

import sys
import math
import heapq

input = sys.stdin.readline

class Vec:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def move(self, x, y):
        return Vec(self.x+x, self.y+y)

    def rotate(self, theta):
        x = self.x * math.cos(theta) - self.y * math.sin(theta)
        y = self.x * math.sin(theta) + self.y * math.cos(theta)
        return Vec(x, y)

    def theta(self):
        if self.x == 0:
            if self.y > 0:
                return math.pi/2
            elif self.y < 0:
                return 3* math.pi / 2
            else:
                return 0
        ret = math.atan(self.y / self.x)
        if self.x < 0:
            ret += math.pi
        return ret

    def dist(self, other):
        return math.sqrt((self.x - other.x)** 2 + (self.y - other.y)** 2)

    def __str__(self):
        return f'{self.x}, {self.y}'


xs, ys, xt, yt = list(map(int, input().split()))
N = int(input())
circles = [(Vec(xs, ys), 0)] # pos, r
for _ in range(N):
    x, y, r = list(map(int, input().split()))
    circles.append((Vec(x, y), r))
circles.append((Vec(xt, yt), 0))

d = [[math.inf]*(N+2) for _ in range(N+2)]
for i in range(N+2):
    for j in range(i, N+2):
        tmp = max(0, circles[i][0].dist(circles[j][0])-(circles[i][1]+circles[j][1]))
        d[i][j] = tmp
        d[j][i] = tmp
q = [(0, 0)]
visited = [False]*(N+2)
ans = math.inf
while q:
    c, i = heapq.heappop(q)
    if visited[i]:
        continue
    if i == N+1:
        print(c)
        return
    visited[i] = True
    for j in range(N+2):
        if visited[j]:
            continue
        heapq.heappush(q, (c+d[i][j], j))


from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
xs,ys,xg,yg = map(int, input().split())
N = int(input())
xyr = [(xs,ys,0)]
xyr.extend([list(map(int, input().split())) for i in range(N)])
xyr.append((xg,yg,0))
graph = [[0] * (N+2) for _ in range(N+2)]

max_val = 10**9

for i in range(N+2):
    graph[i][i] = max_val

for i in range(N+2):
    for j in range(i+1,N+2):
        x1,y1,r1 = xyr[i]
        x2,y2,r2 = xyr[j]
        d = max(0, ((x1-x2)**2 + (y1-y2)**2) ** 0.5 - r1 - r2)
        graph[i][j] = graph[j][i] = d

g = csgraph_from_dense(graph,null_value=max_val)
print(dijkstra(g,indices=0)[-1])

from heapq import heappush,heappop,heapify
INF=10**30

def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for c,v in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                heappush(que,(dist[v],v))
    return dist

sx,sy,gx,gy=map(int,input().split())
N=int(input())
X,Y,R=[sx,gx],[sy,gy],[0,0]
for i in range(N):
    t,m,p=map(int,input().split())
    X.append(t);Y.append(m);R.append(p)
G=[[] for i in range(N+2)]
for i in range(N+2):
    for j in range(i):
        d=max(0,((X[i]-X[j])**2+(Y[i]-Y[j])**2)**0.5-R[i]-R[j])
        G[i].append((d,j))
        G[j].append((d,i))
dist=dijkstra(G,0,N+2)
print(dist[1])

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    xs, ys, xt, yt = list(map(int, input().split()))
    n = int(input())
    XYR = [[xs, ys, 0], [xt, yt, 0]]
    for _ in range(n):
        x, y, r = list(map(int, input().split()))
        XYR.append([x, y, r])

    cost = [[0] * (n + 2) for _ in range(n + 2)]
    for i in range(n + 2):
        x1, y1, r1 = XYR[i]
        for j in range(n + 2):
            x2, y2, r2 = XYR[j]
            dist = max(0, pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5) - (r1 + r2))
            cost[i][j] = cost[j][i] = dist

    def dijkstra(s):
        # 始点sから各頂点への最短距離
        # n:頂点数, cost[u][v]:辺uvのコスト(存在しないときはinf)
        d = [f_inf] * (n + 2)
        used = [False] * (n + 2)
        d[s] = 0

        while True:
            v = -1
            # まだ使われてない頂点の中から最小の距離のものを探す
            for k in range(n + 2):
                if (not used[k]) and (v == -1):
                    v = k
                elif (not used[k]) and d[k] < d[v]:
                    v = k
            if v == -1:
                break
            used[v] = True

            for m in range(n + 2):
                d[m] = min(d[m], d[v] + cost[v][m])
        return d

    res = dijkstra(0)
    print((res[1]))


def __starting_point():
    resolve()

__starting_point()

XS,YS,XT,YT=map(int,input().split())
N=int(input())
V=[[XS,YS,0],[XT,YT,0]]
for i in range(N):
  V.append(list(map(int,input().split())))
INF=10**12
G=[[INF]*len(V) for i in range(len(V))]
def d(a,b):
  return ((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5
for i in range(len(V)):
  G[i][i]=0
  for j in range(len(V)):
    G[i][j]=max(0,d(V[i][:2],V[j][:2])-V[i][2]-V[j][2])
D=[0]*len(V)
U=[0]*len(V)
def ijk(s):
  nonlocal D,U,G,V,INF
  for i in range(len(V)):
    D[i]=INF
    U[i]=False
  D[s]=0
  v=0
  while True:
    v=-1
    for i in range(len(V)):
      if not(U[i]) and (v==-1 or D[i]<D[v]):
        v=i
    if v==-1:
      break
    U[v]=True
    for i in range(len(V)):
      D[i]=min(D[i],D[v]+G[v][i])

ijk(0)
print(D[1])

from heapq import heappop, heappush

sx, sy, tx, ty = list(map(int, input().split()))
n = int(input())
barriers = [tuple(map(int, input().split())) for _ in range(n)]
barriers.append((tx, ty, 0))
barriers.append((sx, sy, 0))
s = n + 1
t = n
q = [(0., s)]
visited = [False] * (n + 2)
while q:
    cost, v = heappop(q)
    if v == t:
        print(cost)
        break
    if visited[v]:
        continue
    visited[v] = True
    vx, vy, vr = barriers[v]
    for u in range(n + 1):
        if visited[u]:
            continue
        ux, uy, ur = barriers[u]
        new_cost = max(0, ((vx - ux) ** 2 + (vy - uy) ** 2) ** 0.5 - vr - ur)
        heappush(q, (cost + new_cost, u))


from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    x_s, y_s, x_t, y_t = list(map(int, readline().split()))
    A = np.array([[x_s, y_s, 0],
                  [x_t, y_t, 0]], dtype=np.int)
    
    N = int(readline())
    B = np.array(read().split(), dtype=np.int).reshape(-1, 3)
    XY, R = np.hsplit(np.concatenate((A, B)), [2])
    
    d = np.expand_dims(XY, axis=1) - np.expand_dims(XY, axis=0)
    d = np.sqrt(np.sum(d ** 2, axis=-1))
    d -= R + R.reshape(1, -1)
    d = np.maximum(d, 0)
    np.fill_diagonal(d, -1)
    d = csgraph_from_dense(d, null_value=-1)
     
    ans = dijkstra(d, indices=0)[1]
    print(ans)


def __starting_point():
    main()

__starting_point()

from math import sqrt

xs, ys, xt, yt = map(int, input().split())
n = int(input())
xyr = [list(map(int, input().split())) for i in range(n)]
xyr.insert(0, [xs, ys, 0])
xyr.append([xt, yt, 0])
Graph = [[0] * (n + 2) for i in range(n + 2)]
for i in range(n + 2):
    for j in range(n + 2):
        Graph[i][j] = max(0, sqrt((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) - (xyr[i][2] + xyr[j][2]))
INF = 10 ** 18
dist = [INF] * (n + 2)
visited = [False] * (n + 2)
dist[0] = 0
while True:
    v = -1
    for i in range(n + 2):
        if not visited[i] and (v == -1 or dist[i] < dist[v]):
            v = i
    if v == -1:
        break
    visited[v] = True
    for i in range(n + 2):
        dist[i] = min(dist[i], dist[v] + Graph[v][i])
print(dist[-1])

sx,sy,tx,ty=map(int,input().split())
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
l.append([sx,sy,0])
l.append([tx,ty,0])

def dijkstra(s,n,cost):
  d=[float("inf")]*n
  used=[False]*n
  d[s]=0
  while True:
    v=-1
    for i in range(n):
      if (not used[i]) and (v==-1):
        v=i
      elif (not used[i]) and d[i]<d[v]:
        v=i
    if v==-1:
      break
    used[v]=True
    for j in range(n):
      d[j]=min(d[j],d[v]+cost[v][j])
  return d

cost=[[float("inf") for i in range(n+2)] for i in range(n+2)] 
for i in range(n+2):
  for j in range(n+2):
    cost[i][j]=max(((l[i][0]-l[j][0])**2+(l[i][1]-l[j][1])**2)**0.5-l[i][2]-l[j][2],0)
    cost[j][i]=max(((l[i][0]-l[j][0])**2+(l[i][1]-l[j][1])**2)**0.5-l[i][2]-l[j][2],0)
print(dijkstra(n,n+2,cost)[n+1])

# Cosmic rays
import math
import heapq

xs, ys, xt, yt = map(int, input().split())
N = int(input())

d = [((xs, ys), 0, 0)]
# node,radius

for _ in range(N):
    x, y, r = map(int, input().split())
    d.append(((x, y), _+1, r))

graph = {i: [] for i in range(N+2)}

d.append(((xt, yt), N+1, 0))
for i in range(N+2):
    for j in range(i+1, N+2):
        p, point, rad = d[i]
        q, point2, rad2 = d[j]
        D = math.hypot(p[0]-q[0], p[1]-q[1])
        if D > (rad+rad2):
            graph[i].append((D-rad-rad2, j))
            graph[j].append((D-rad-rad2, i))
        else:
            graph[i].append((0, j))
            graph[j].append((0, i))


def dijkstra(s, graph):
    n = len(graph)
    dist = [float("inf") for i in range(n+1)]
    dist[s] = 0
    pq = []
    heapq.heapify(pq)
    heapq.heappush(pq, (0, s))
    while pq:
        mini_dis, node = heapq.heappop(pq)
        if dist[node] < mini_dis:
            continue
        for w, point in graph[node]:
            if dist[point] < w:
                continue
            newlen = dist[node]+w
            if newlen < dist[point]:
                heapq.heappush(pq, (newlen, point))
                dist[point] = newlen
    return dist

K=dijkstra(0,graph)[N+1]
print(K)

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  # 優先度付きキューを使わないダイクストラ
  xs,ys,xt,yt=list(map(int,input().split()))
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print((seen[n+1]))
def __starting_point():
  main()

__starting_point()

from heapq import heappush, heappop

sX, sY, tX, tY = list(map(int, input().split()))
N = int(input())

XYR = [tuple(map(int, input().split())) for _ in range(N)] + [(sX, sY, 0), (tX, tY, 0)]
S, T = N, N + 1
N += 2

edges = [[] for _ in range(N)]
for i, (x, y, r) in enumerate(XYR):
    for j, (u, v, w) in enumerate(XYR[i + 1:], start=i + 1):
        dist = max(0, ((x - u)**2 + (y - v)**2)**0.5 - (r + w))
        edges[i].append((j, dist))
        edges[j].append((i, dist))

minDist = [10**18] * N
minDist[S] = 0
que = [(0, S)]
while que:
    dist, now = heappop(que)
    if minDist[now] < dist:
        continue
    for to, cost in edges[now]:
        d = dist + cost
        if minDist[to] > d:
            minDist[to] = d
            heappush(que, (d, to))
print((minDist[T]))


import sys
import heapq
my_input = sys.stdin.readline

def main():
    xs, ys, xt, yt = list(map(int, my_input().split()))
    N = int(my_input())
    C = [(xs, ys, 0), (xt, yt, 0)]
    C += [tuple(map(int, my_input().split())) for i in range(N)]

    G = [[] for i in range(N+2)]
    for i in range(N + 2):
        for j in range(i + 1, N + 2):
            cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
            G[i].append((j, cost))
            G[j].append((i, cost))


    def dijkstra(graph, start, inf=float('inf')):
        import heapq
        n = len(graph)
        distances = [inf] * n
        distances[start] = 0
        visited = [False] * n

        # 距離・頂点
        hq = [(0, start)]
        while hq:
            dist, fr = heapq.heappop(hq)
            if distances[fr] < dist:
                continue
            if fr == 1:
                return distances
            visited[fr] = True

            for to, cost in graph[fr]:
                new_dist = distances[fr] + cost
                if (visited[to]) or (distances[to] <= new_dist):
                    continue

                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

        return distances


    dist = dijkstra(G, 0)
    print((dist[1]))


def __starting_point():
    main()

__starting_point()

def main():
    from math import hypot
    import sys
    input = sys.stdin.readline

    inf = 1 << 60

    xs, ys, xt, yt = list(map(int, input().split()))
    N = int(input())
    N += 2

    def dist(p1, p2):
        d = hypot(p1[0] - p2[0], p1[1] - p2[1])
        return max(0, d - (p1[2] + p2[2]))

    s = (xs, ys, 0, 0)
    g = (xt, yt, 0, N - 1)
    ps = [s, g]  # x,y,r,idx
    adj = [[inf] * N for _ in range(N)]
    adj[0][N - 1] = adj[N - 1][0] = dist(s, g)
    for idx1 in range(1, N - 1):
        *p1, = list(map(int, input().split()))  # x,y,r
        p1.append(idx1)
        for *p2, idx2 in ps:
            d = dist(p1, p2)
            adj[idx1][idx2] = adj[idx2][idx1] = d
        ps.append(p1)

    def dijkstra(s):
        from heapq import heappop, heappush

        dist = [inf] * N

        h = [(0, s)]  # c,v
        dist[s] = 0

        while h:
            c, v = heappop(h)
            if dist[v] < c: continue

            for u, dc in enumerate(adj[v]):
                nc = c + dc
                if dist[u] <= nc: continue
                dist[u] = nc
                heappush(h, (nc, u))

        return dist

    print((dijkstra(s=0)[N - 1]))


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
import sys


def solve(x_s: int, y_s: int, x_t: int, y_t: int, N: int, x: "List[int]", y: "List[int]", r: "List[int]"):
    import numpy as np
    from scipy.sparse import csr_matrix
    from scipy.sparse.csgraph import dijkstra
    x.extend([x_s, x_t])
    y.extend([y_s, y_t])
    r.extend([0, 0])
    p = np.column_stack((x, y))
    diff = np.expand_dims(p, axis=1) - np.expand_dims(p, axis=0)
    dist = np.sqrt(np.sum(diff ** 2, axis=-1))
    delta = 0.5
    mat = csr_matrix(((dist - r).T - r).clip(min=0)-delta)
    mat.data += delta
    return dijkstra(mat, indices=N)[N+1]

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    x_s = int(next(tokens))  # type: int
    y_s = int(next(tokens))  # type: int
    x_t = int(next(tokens))  # type: int
    y_t = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    r = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        r[i] = int(next(tokens))
    print((solve(x_s, y_s, x_t, y_t, N, x, y, r)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

#!/usr/bin/env python3
import sys


def solve(x_s: int, y_s: int, x_t: int, y_t: int, N: int, x: "List[int]", y: "List[int]", r: "List[int]"):
    import numpy as np
    from scipy.sparse import csr_matrix, coo_matrix
    from scipy.sparse.csgraph import dijkstra
    x.extend([x_s, x_t])
    y.extend([y_s, y_t])
    r.extend([0, 0])
    p = np.column_stack((x, y))
    diff = np.expand_dims(p, axis=1) - np.expand_dims(p, axis=0)
    dist = np.sqrt(np.sum(diff ** 2, axis=-1))
    mat = ((dist - r).T - r).clip(min=1e-20)    
    return '{:.10f}'.format(dijkstra(csr_matrix(mat), indices=N)[N+1])

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    x_s = int(next(tokens))  # type: int
    y_s = int(next(tokens))  # type: int
    x_t = int(next(tokens))  # type: int
    y_t = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    r = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        r[i] = int(next(tokens))
    print((solve(x_s, y_s, x_t, y_t, N, x, y, r)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

def main():
    from math import hypot
    import sys
    input = sys.stdin.readline

    inf = 1 << 60

    xs, ys, xt, yt = list(map(int, input().split()))
    N = int(input())

    def dist(p1, p2):
        d = hypot(p1[0] - p2[0], p1[1] - p2[1])
        return max(0, d - (p1[2] + p2[2]))

    ps = [(xs, ys, 0)]
    ps += (tuple(map(int, input().split())) for _ in range(N))
    ps += [(xt, yt, 0)]

    adj = [[inf] * (N + 2) for _ in range(N + 2)]

    for i, p1 in enumerate(ps):
        for j, p2 in enumerate(ps):
            if i <= j: break  # 自己辺なし
            adj[i][j] = adj[j][i] = dist(p1, p2)

    def dijkstra(s):
        dist = [inf] * (N + 2)
        dist[s] = 0
        det = [0] * (N + 2)

        c, v = 0, s
        det[s] = 1
        for _ in range(N + 1):
            for u, dc in enumerate(adj[v]):
                nc = c + dc
                if dist[u] <= nc: continue
                dist[u] = nc

            c, v = -1, -1
            for u, d in enumerate(dist):
                if det[u]: continue
                if ~v and c <= d: continue
                c, v = d, u
            det[v] = 1

        return dist

    print((dijkstra(s=0)[N + 1]))


def __starting_point():
    main()

__starting_point()

import heapq
INFTY = 10**10
def f(x,y):
    return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5
xs,ys,xt,yt = map(int,input().split())
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
A.insert(0,[xs,ys,0])
A.append([xt,yt,0])
dist = [INFTY for _ in range(N+2)]
hist = [0 for _ in range(N+2)]
heap = [(0,0)]
dist[0]=0
hist[0]=1
while heap:
    d,x = heapq.heappop(heap)
    if dist[x]<d:continue
    hist[x]=1
    for i in range(N+2):
        if hist[i]==0:
            if dist[i]>d+max(f(A[x][:2],A[i][:2])-(A[x][2]+A[i][2]),0):
                dist[i]=d+max(f(A[x][:2],A[i][:2])-(A[x][2]+A[i][2]),0)
                heapq.heappush(heap,(dist[i],i))
print(dist[N+1])

from math import sqrt
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

xs, ys, xt, yt = list(map(int, input().split()))
n = int(input())
xyr = [list(map(int, input().split())) for _ in range(n)]

xyr.append([xs, ys, 0])
xyr.append([xt, yt, 0])

row = []
col = []
cost = []

for i, (xi, yi, ri) in enumerate(xyr):
    for j, (xj, yj, rj) in enumerate(xyr[i+1:], i+1):
        row.append(i)
        col.append(j)
        dist = max(0, sqrt((xi - xj) ** 2 + (yi - yj) ** 2) - ri - rj)
        cost.append(dist)

g = csr_matrix((cost, (row, col)), shape=(n + 2, n + 2))
d = dijkstra(g, directed=False, indices=n)
ans = d[n+1]
print(ans)


import sys
input = sys.stdin.readline

def dijkstra(edges, size, src):
    from heapq import heappush, heappop

    INF = 10**18
    dist = [INF] * size
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, v = heappop(pq)
        if d > dist[v]:
            continue
        for u, weight in edges[v]:
            nd = d + weight
            if dist[u] > nd:
                dist[u] = nd
                heappush(pq, (nd, u))
    return dist

xs, ys, xt, yt = map(int, input().split())
N = int(input())
xyr = [tuple(map(int, input().split())) for _ in range(N)]
xyr.append((xs, ys, 0))
xyr.append((xt, yt, 0))
edges = [[] for _ in range(N+2)]
for i in range(N+1):
    for j in range(i, N+2):
        xi, yi, ri = xyr[i]
        xj, yj, rj = xyr[j]
        d = max(0, ((xj-xi)**2 + (yj-yi)**2)**0.5 - (ri + rj))
        edges[i].append((j, d))
        edges[j].append((i, d))
d = dijkstra(edges, N+2, N)
print(d[N+1])