Buggy python submission (verdict: Runtime Error):
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

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

p = [(xs,ys,0),(xt,yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
edge = [[-1]*(n+2)for i in range(n+2)]
 
for i in range(n+2):
    for j in range(i+1,n+2):
        edge[i][j] = edge[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0.0)

G = csgraph_from_dense(edge,null_value=-1)
print(dijkstra(G,indices=0)[1])

#print(d[1])


Fixed submission:
Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
n += 2
s = 0
#始点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])
print(d[1])

Buggy python submission (verdict: Runtime Error):
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

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

p = [(xs,ys,0),(xt,yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
edge = [[0]*(n+2)for i in range(n+2)]
 
for i in range(n+2):
    for j in range(i+1,n+2):
        edge[i][j] = edge[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0.0)

edge = csgraph_from_dense(edge,null_value=None)
d = dijkstra(edge,directed=False,indices=0)

print(d[1])


Fixed submission:
Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
n += 2
s = 0
#始点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])
print(d[1])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

INF = 10 ** 20

xs, ys, xt, yt = map(int, input().split())
N = int(input())
X = np.zeros((1, N + 2), dtype=np.float64)
Y = np.zeros((1, N + 2), dtype=np.float64)
R = np.zeros((1, N + 2), dtype=np.float64)

X[0][0] = xs
Y[0][0] = ys
X[0][N + 1] = xt
Y[0][N + 1] = yt

for i in range(N):
    X[0][i + 1], Y[0][i + 1], R[0][i + 1] = map(int, input().split())

# G[i][j]: iからjまでの距離
G = np.maximum(np.sqrt(np.square(X - X.T) + np.square(Y - Y.T)) - (R + R.T),
               np.zeros((N + 2, N + 2), dtype=np.float64))
# 対角行列をinfで塗りつぶす
G += np.diag(np.ones(N + 2, dtype=np.float64) * np.inf)
# 自己ループを消す
G = csgraph_from_dense(G, null_value=np.inf)
print(dijkstra(G)[0][-1])


Fixed submission:
Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
n += 2
s = 0
#始点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])
print(d[1])

Buggy python submission (verdict: Runtime Error):
def dijkstra(s):
    #始点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

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [([Xs,Ys,0],[Xt,Yt,0]]
for i in range(2,n+2):
    p.append(list(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)

n += 2

res = dijkstra(0)
print(1)


Fixed submission:
Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
n += 2
s = 0
#始点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])
print(d[1])

Buggy python submission (verdict: Runtime Error):
def dijkstra(s):
    #始点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
 
Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [[Xs,Ys,0],[Xt,Yt,0]]
for i in range(2,n+2):
    p.append(map(int,input().split()))
cost = [[0]*(n+2)for i in range(n+2)]
 
for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
#cost = tuple(cost)
n += 2
 
res = dijkstra(0)
print(1)

Fixed submission:
Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
n += 2
s = 0
#始点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])
print(d[1])

Buggy python submission (verdict: Time Limit Exceeded):
def dijkstra(s,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

def dis(p,q):
    cand = ((x[p]-x[q])**2+(y[p]-y[q])**2)**0.5 - r[p] - r[q]
    return max(cand,0)
    

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
x = [0]*(n+2)
y = [0]*(n+2)
r = [0]*(n+2)
x[0] = Xs
y[0] = Ys
x[1] = Xt
y[1] = Yt
for i in range(2,n+2):
    x[i],y[i],r[i] = map(int,input().split())
edge = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        edge[i][j] = dis(i,j)
        edge[j][i] = dis(i,j)
n += 2
res = dijkstra(0,edge)
print(res[1])

Fixed submission:
Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
n += 2
s = 0
#始点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])
print(d[1])

Buggy python submission (verdict: Time Limit Exceeded):
#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

def dis(p,q):
    cand = ((x[p]-x[q])**2+(y[p]-y[q])**2)**0.5 - r[p] - r[q]
    return max(cand,0)
    

Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
x = [0]*(n+2)
y = [0]*(n+2)
r = [0]*(n+2)
x[0] = Xs
y[0] = Ys
x[1] = Xt
y[1] = Yt
for i in range(2,n+2):
    x[i],y[i],r[i] = map(int,input().split())
edge = [[[0,0] for j in range(n+2)]for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        edge[i][j] = [dis(i,j),j]
        edge[j][i] = [dis(i,j),i]
n += 2
res = dijkstra_heap(0)
print(res[1])

Fixed submission:
Xs,Ys,Xt,Yt = map(int,input().split())
n = int(input())
p = [(Xs,Ys,0),(Xt,Yt,0)]
for i in range(2,n+2):
    p.append(tuple(map(int,input().split())))
cost = [[0]*(n+2)for i in range(n+2)]

for i in range(n+2):
    for j in range(i,n+2):
        cost[i][j] = cost[j][i] =  max(((p[i][0]-p[j][0])**2+(p[i][1]-p[j][1])**2)**0.5 - p[i][2] - p[j][2],0)
n += 2
s = 0
#始点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])
print(d[1])