Problem:
 Score : 600 points    Problem Statement On the x y -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 1 -2 -2 2 2
1
0 0 1      Sample Output 1 3.6568542495  An optimal route is as follows:          Sample Input 2 -2 0 2 0
2
-1 0 2
1 0 2      Sample Output 2 0.0000000000  An optimal route is as follows:          Sample Input 3 4 -2 -2 4
3
0 0 2
4 0 1
0 4 1      Sample Output 3 4.0000000000  An optimal route is as follows:

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

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

xs, ys, xt, yt = map(int, readline().split())
n = int(readline())
xyr = np.array(read().split(), np.int64)
xyr = np.append(xyr, [xs, ys, 0, xt, yt, 0])
xyr = xyr.reshape((-1, 3))

xy = xyr[:, :2]
dist = cdist(xy, xy)
r = xyr[:, 2]
dist = np.maximum(dist - r - r.reshape((-1, 1)), 0)
dist[np.arange(n+2), np.arange(n+2)] = np.inf
g = csgraph_from_dense(dist, null_value=np.inf)

ans = dijkstra(g, indices=n)[n+1]
print(ans)

Solution (Python):
from math import sqrt
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

xs, ys, xt, yt = 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)

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

    import heapq
    def dijkstra_heap(s,g,edge):
        
        d = [10**20] * (n+2)
        used = [True] * (n+2) 
        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=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))

if __name__ == '__main__':
    resolve()

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

    import heapq
    def dijkstra_heap(s,g,edge):
        
        d = [10**20] * (n+2)
        used = [True] * (n+2) 
        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=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))

if __name__ == '__main__':
    main()

Solution (Python):
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])

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
def hypot(x1, y1, x2, y2):
  return ((x1-x2)**2 + (y1-y2)**2) ** 0.5
INF = 2**31 - 1
sx, sy, ex, ey = map(int, input().split())
n = int(input())
XYR = [list(map(int, input().split())) for _ in range(n)]
G = [[INF]*(n+2) for _ in range(n+2)]
for i in range(n-1):
  for j in range(i+1, n):
    x1, y1, r1 = XYR[i]
    x2, y2, r2 = XYR[j]
    d = hypot(x1, y1, x2, y2)
    k = max(d-r1-r2, 0)
    G[i][j] = k
for i, xyr in enumerate(XYR):
  x, y, r = xyr
  ds = hypot(sx, sy, x, y)
  de = hypot(ex, ey, x, y)
  ks = max(ds-r, 0)
  ke = max(de-r, 0)
  G[i][n] = ks
  G[i][n+1] = ke
G[n][n+1] = hypot(sx, sy, ex, ey)
C = csgraph_from_dense(G, null_value=INF)
D = dijkstra(C, indices=n, directed=False)
ans = D[n+1]
print(ans)

Solution (Python):
from math import hypot
def dijkstra(s):
    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


sx, sy, gx, gy = map(int,input().split())
n = int(input())
edge = [(sx, sy, 0)]

for i in range(n):
    x, y, r = map(int,input().split())
    edge.append((x,y,r))
edge.append((gx, gy, 0))

cost = [[0] * (n + 2) for _ in range(n + 2)]
for j, (k1, k2, k3) in enumerate(edge):
    for l, (m1, m2, m3) in enumerate(edge):
        if j == l:
            continue
        else:
            cost[j][l] = max(hypot(k1 - m1, k2 - m2) - k3 - m3, 0)
n += 2

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

Solution (Python):


def dijkstra(s):
    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


sx, sy, gx, gy = map(int,input().split())
n = int(input())
edge = [[sx, sy, 0]]

for i in range(n):
    x, y, r = map(int,input().split())
    edge.append([x,y,r])
edge.append([gx, gy, 0])

cost = [[0] * (n + 2) for _ in range(n + 2)]
for j, k in enumerate(edge):
    for l, m in enumerate(edge):
        if j == l:
            continue
        else:
            cost[j][l] = max(((k[0]-m[0])**2+(k[1]-m[1])**2)**0.5-k[2]-m[2], 0)
n += 2

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

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))





from heapq import heappop, heappush
def dijkstra(E,s,n):
    d = [float('inf')]*n
    d[s] = 0
    q = []
    heappush(q,(0,s))
    while q:
        du,u = heappop(q)
        if d[u] < du:
            continue
        for v,weight in E[u].items():
            dnew = du + weight
            if d[v] > dnew:
                d[v] = dnew
                heappush(q,(dnew,v))
    return d


def dist_two_circles(c1,r1,c2,r2):
    dist2 = (c1[0]-c2[0])**2 + (c1[1]-c2[1])**2
    if dist2 > (r1+r2)**2:
        return dist2**0.5-r1-r2
    else:
        return 0.0


def dist_point_circle(x0,y0,c,r):
    dist2 = (c[0]-x0)**2 + (c[1]-y0)**2
    if dist2 > r**2:
        return dist2**0.5-r
    else:
        return 0.0

xs,ys,xt,yt = LI()
N = I()
x,y,r = LIR(N,3)

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

for i in range(N):
    for j in range(i+1,N):
        ci = (x[i],y[i])
        cj = (x[j],y[j])
        dist = dist_two_circles(ci,r[i],cj,r[j])
        E[i+1][j+1] = dist
        E[j+1][i+1] = dist

for i in range(N):
    ci = (x[i],y[i])
    dist_s = dist_point_circle(xs,ys,ci,r[i])
    E[0][i+1] = dist_s
    dist_t = dist_point_circle(xt,yt,ci,r[i])
    E[i+1][N+1] = dist_t

E[0][N+1] = ((xs-xt)**2 + (ys-yt)**2)**0.5

d = dijkstra(E,0,N+2)
print(d[N+1])

Solution (Python):
xs,ys,xg,yg = map(int, input().split())
n = int(input())
xyr=[list(map(int,input().split())) for i in range(n)]

import math
from collections import defaultdict
link = defaultdict(list)
dist = math.sqrt((xs-xg)**2 + (ys-yg)**2)
link[10000].append([20000,dist])

for i in range(n):
    x,y,r = xyr[i]

    dist = math.sqrt((x-xs)**2 + (y-ys)**2) - r
    dist = max(0,dist)
    link[10000].append([i,dist])

    dist = math.sqrt((x-xg)**2 + (y-yg)**2) - r
    dist = max(0,dist)
    link[i].append([20000,dist])

for i in range(n):
    for j in range(i+1,n):
        x1,y1,r1=xyr[i]
        x2,y2,r2=xyr[j]

        dist = math.sqrt((x1-x2)**2 + (y1-y2)**2) - r1 - r2
        dist = max(0,dist)
        link[i].append([j,dist])
        link[j].append([i,dist])

from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
def dks(g,start):
    visited = set()
    hq = []
    heappush(hq, (0,start))

    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        cost[i] = shortest
        for j, t in g[i]:
            if j in visited:
                continue
            heappush(hq, (shortest + t, j))
    return cost

res = dks(link,10000)
print(res[20000])

Solution (Python):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  
        self._E = 0  
        self._V = V  

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                
                e = self.G[v][i]  
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  
                    heapq.heappush(que, (d[e.to], e.to))  
        return d

from math import sqrt

xs,ys,xt,yt=map(int,input().split())
N=int(input())
pro=Dijkstra(N+2)
node=[(xs,ys,0),(xt,yt,0)]
for i in range(0,N):
    x,y,r=map(int,input().split())
    node.append((x,y,r))

for i in range(0,N+2):
    for j in range(0,N+2):
        x1,y1,r1=node[i]
        x2,y2,r2=node[j]
        cost=max(0,sqrt((x1-x2)**2+(y1-y2)**2)-r1-r2)
        pro.add(i,j,cost)

ans=pro.shortest_path(0)
print(ans[1])

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


sx, sy, gx, gy = lr()
N = ir()
XYR = [[sx, sy, 0]] + [lr() for _ in range(N)] + [[gx, gy, 0]]
graph = [[] for _ in range(N+2)]  
for i in range(N+2):
    for j in range(i+1, N+2):
        sp = XYR[i]; ep = XYR[j]
        length = max(0, ((sp[0]-ep[0]) ** 2 + (sp[1]-ep[1]) ** 2) ** .5 - sp[2] - ep[2])
        graph[i].append((j, length))
        graph[j].append((i, length))

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * (N+2)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, l in graph[prev]:
            d1 = d + l
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

dist = dijkstra(0)
answer = dist[N+1]
print(answer)

Solution (Python):

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


sx, sy, gx, gy = lr()
N = ir()
XYR = [[sx, sy, 0]] + [lr() for _ in range(N)] + [[gx, gy, 0]]
graph = [[] for _ in range(N+2)]  
for i in range(N+2):
    for j in range(i+1, N+2):
        sp = XYR[i]; ep = XYR[j]
        length = max(0, ((sp[0]-ep[0]) ** 2 + (sp[1]-ep[1]) ** 2) ** .5 - sp[2] - ep[2])
        graph[i].append((j, length))
        graph[j].append((i, length))

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * (N+2)
    dist[start] = 0
    que = [(0, start)]
    visited = set()
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, l in graph[prev]:
            if next == prev or next in visited:
                continue
            d1 = d + l
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
        visited.add(prev)
    return dist

dist = dijkstra(0)
answer = dist[N+1]
print(answer)

Solution (Python):
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else 1<<33) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


sx,sy,gx,gy=LI()
n=I()
 
c=[(sx,sy,0),(gx,gy,0)]
for i in range(n):
    c+=[LI()]

n+=2
g=[[]for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        x,y,r1=c[i]
        s,t,r2=c[j]
        d=math.hypot(x-s,y-t) -r1 -r2
        if d<0:d=0
        g[i].append((j,d))
        g[j].append((i,d))
d,_=dijkstra(g,0)
print(d[1])

Solution (Python):
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)


def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


sx,sy,gx,gy=LI()
n=I()
 
c=[(sx,sy,0),(gx,gy,0)]
for i in range(n):
    c+=[LI()]

n+=2
g=[[]for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        x,y,r1=c[i]
        s,t,r2=c[j]
        d=math.hypot(x-s,y-t) -r1 -r2
        if d<0:d=0
        g[i].append((j,d))
        g[j].append((i,d))
d,_=dijkstra(g,0)
print(d[1])