Buggy python submission (verdict: Time Limit Exceeded):
import sys
from math import sqrt
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
INF = float('inf')
cost = [[INF] * (N + 2) for i in range(N + 2)]
D = []
D.append((xs, ys, 0))
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xt, yt, 0))

for i in range(N + 2):
    for j in range(i + 1, N + 2):
        k = max(0, sqrt((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) - D[i][2] - D[j][2])
        cost[i][j] = k
        cost[j][i] = k

d = [INF] * (N + 2)
d[0] = 0
que = [(0, 0.0)]
while que:
    v, dist = heappop(que)
    if d[v] < dist:
        continue
    if v == N + 1:
        print(d[v])
        exit()
    for w in range(N + 2):
        if w != v and d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (w, d[w]))



Fixed submission:
import sys
from math import sqrt
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
INF = float('inf')
cost = [[INF] * (N + 2) for i in range(N + 2)]
D = [(xs, ys, 0)]
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xt, yt, 0))

for i in range(N + 2):
    for j in range(i + 1, N + 2):
        k = max(0, sqrt((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) - D[i][2] - D[j][2])
        cost[i][j] = k
        cost[j][i] = k

visit = [0] * (N + 2)
visit[0] = 1
d = [INF] * (N + 2)
d[0] = 0
que = [(0, 0)]
while que:
    dist, v = heappop(que)
    if d[v] < dist:
        continue
    if v == N + 1:
        print(d[v])
        exit()
    visit[v] = 1
    for w in range(N + 2):
        if visit[w] == 0 and w != v and d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (d[w], w))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
cost = [[0] * (N + 2) for i in range(N + 2)]
D = []
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xs, ys, 0))
D.append((xt, yt, 0))

for i in range(len(D)):
    for j in range(i + 1, len(D)):
        k = max(0, ((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) ** 0.5 - (D[i][2] + D[j][2]))
        cost[i][j] = k
        cost[j][i] = k
INF = float('inf')
d = [INF] * (N + 2)
d[N] = 0
que = [(N, 0.0)]
while que:
    v, dist = heappop(que)
    if d[v] < dist:
        continue
    if v == N + 1:
        print(d[N + 1])
        exit()
    for w in range(N + 2):
        if d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (w, d[w]))


Fixed submission:
import sys
from math import sqrt
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
INF = float('inf')
cost = [[INF] * (N + 2) for i in range(N + 2)]
D = [(xs, ys, 0)]
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xt, yt, 0))

for i in range(N + 2):
    for j in range(i + 1, N + 2):
        k = max(0, sqrt((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) - D[i][2] - D[j][2])
        cost[i][j] = k
        cost[j][i] = k

visit = [0] * (N + 2)
visit[0] = 1
d = [INF] * (N + 2)
d[0] = 0
que = [(0, 0)]
while que:
    dist, v = heappop(que)
    if d[v] < dist:
        continue
    if v == N + 1:
        print(d[v])
        exit()
    visit[v] = 1
    for w in range(N + 2):
        if visit[w] == 0 and w != v and d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (d[w], w))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
cost = [[0] * (N + 2) for i in range(N + 2)]
D = []
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xs, ys, 0))
D.append((xt, yt, 0))

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

INF = float('inf')
d = [INF] * (N + 2)
d[N] = 0
que = [(N, 0.0)]
while que:
    v, dist = heappop(que)
    if d[v] < dist:
        continue
    for w in range(N + 2):
        if d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (w, d[w]))

print(d[N + 1])

Fixed submission:
import sys
from math import sqrt
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
INF = float('inf')
cost = [[INF] * (N + 2) for i in range(N + 2)]
D = [(xs, ys, 0)]
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xt, yt, 0))

for i in range(N + 2):
    for j in range(i + 1, N + 2):
        k = max(0, sqrt((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) - D[i][2] - D[j][2])
        cost[i][j] = k
        cost[j][i] = k

visit = [0] * (N + 2)
visit[0] = 1
d = [INF] * (N + 2)
d[0] = 0
que = [(0, 0)]
while que:
    dist, v = heappop(que)
    if d[v] < dist:
        continue
    if v == N + 1:
        print(d[v])
        exit()
    visit[v] = 1
    for w in range(N + 2):
        if visit[w] == 0 and w != v and d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (d[w], w))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
cost = [[0] * (N + 2) for i in range(N + 2)]
D = []
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xs, ys, 0))
D.append((xt, yt, 0))

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

INF = float('inf')
d = [INF] * (N + 2)
d[N] = 0
que = [(N, 0.0)]
while que:
    v, dist = heappop(que)
    if d[v] < dist:
        continue
    for w in range(N + 2):
        if d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (w, d[w]))

print(d[N + 1])



Fixed submission:
import sys
from math import sqrt
input = sys.stdin.readline
from heapq import heappop, heappush
xs, ys, xt, yt = map(int, input().split())
N = int(input())
INF = float('inf')
cost = [[INF] * (N + 2) for i in range(N + 2)]
D = [(xs, ys, 0)]
for i in range(N):
    x, y, r = map(int, input().split())
    D.append((x, y, r))
D.append((xt, yt, 0))

for i in range(N + 2):
    for j in range(i + 1, N + 2):
        k = max(0, sqrt((D[i][0] - D[j][0]) ** 2 + (D[i][1] - D[j][1]) ** 2) - D[i][2] - D[j][2])
        cost[i][j] = k
        cost[j][i] = k

visit = [0] * (N + 2)
visit[0] = 1
d = [INF] * (N + 2)
d[0] = 0
que = [(0, 0)]
while que:
    dist, v = heappop(que)
    if d[v] < dist:
        continue
    if v == N + 1:
        print(d[v])
        exit()
    visit[v] = 1
    for w in range(N + 2):
        if visit[w] == 0 and w != v and d[w] > d[v] + cost[v][w]:
            d[w] = d[v] + cost[v][w]
            heappush(que, (d[w], w))