Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

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

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

graph[0][-1] = graph[-1][0] = dist(xs, ys, xt, yt)
for i, (xi, yi, ri) in enumerate(xyr, 1):
  d1 = max(0, dist(xs, ys, xi, yi) - ri)
  d2 = max(0, dist(xt, yt, xi, yi) - ri)
  graph[0][i] = graph[i][0] = d1
  graph[-1][i] = graph[i][-1] = d2
  for j, (xj, yj, rj) in enumerate(xyr, 1):
    dij = max(0, dist(xi, yi, xj, yj) - ri -rj)
    graph[i][j] = graph[j][i] = dij

INF = 10**15
d = [INF] * (N+2)
d[0] = 0
h = []
for i, di in enumerate(graph[0][1:], 1):
  heappush(h, [di, i])

while h:
  di, i = heappop(h)
  if d[i] < INF:
    continue
  d[i] = di
  if i == N+1:
    print(di)
    quit()
  for j, dj in enumerate(graph[i]):
    if d[j] < INF or j == i:
      continue
    heappush(h, [d[i]+dj, j])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop

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

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

graph[0][-1] = graph[-1][0] = dist(xs, ys, xt, yt)
for i, (xi, yi, ri) in enumerate(xyr, 1):
  d1 = max(0, dist(xs, ys, xi, yi) - ri)
  d2 = max(0, dist(xt, yt, xi, yi) - ri)
  graph[0][i] = graph[i][0] = d1
  graph[-1][i] = graph[i][-1] = d2
  for j, (xj, yj, rj) in enumerate(xyr, 1):
    dij = max(0, dist(xi, yi, xj, yj) - ri -rj)
    graph[i][j] = graph[j][i] = dij

INF = 10**15
d = [INF] * (N+2)
d[0] = 0
h = []
for i, di in enumerate(graph[0][1:], 1):
  heappush(h, [di, i])

while h:
  di, i = heappop(h)
  if d[i] < INF:
    continue
  d[i] = di
  if i == N+1:
    print(di)
    quit()
  for j, dj in enumerate(graph[i]):
    if j == i:
      continue
    if d[j] < INF:
      continue
    heappush(h, [d[i]+dj, j])

Fixed submission:
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])

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop

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

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

graph[0][-1] = graph[-1][0] = dist(xs, ys, xt, yt)
for i, (xi, yi, ri) in enumerate(xyr, 1):
  d1 = max(0, dist(xs, ys, xi, yi) - ri)
  d2 = max(0, dist(xt, yt, xi, yi) - ri)
  graph[0][i] = graph[i][0] = d1
  graph[-1][i] = graph[i][-1] = d2
  for j, (xj, yj, rj) in enumerate(xyr, 1):
    dij = max(0, dist(xi, yi, xj, yj) - ri -rj)
    graph[i][j] = graph[j][i] = dij

INF = 10**15
d = [INF] * (N+2)
d[0] = 0
h = []
for i, di in enumerate(graph[0][1:], 1):
  heappush(h, [di, i])

while h:
  di, i = heappop(h)
  if d[i] < INF:
    continue
  d[i] = di
  if i == N+1:
    print(di)
    quit()
  for j, dj in enumerate(graph[i]):
    if j == i:
      continue
    if d[j] < INF:
      continue
    heappush(h, [d[i]+dj, j])

Fixed submission:
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])