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

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
N += 2
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
E = [[float('inf')] * N for _ in range(N)]
for v in range(N): E[v][v] = 0
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    E[i][j] = E[j][i] = d
dist = [float('inf')] * N # the distance of each vertex from s
visited = [False] * N
n_visited = 0 # #(visited vertices)
heap = []
heappush(heap, (0, -1, 0))
while heap:
    d, p, v = heappop(heap)
    if visited[v]: continue # (s,v)-shortest path is already calculated
    dist[v] = d; visited[v] = True
    n_visited += 1
    if n_visited == N: break
    for u in range(N):
        if visited[u]: continue
        temp = d + E[v][u]
        if dist[u] > temp: heappush(heap, (temp, v, u))
print(dist[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Buggy python submission (verdict: Runtime Error):
from itertools import combinations
from heapq import heappush, heappop

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
E = [[float('inf')] * (N+2) for _ in range(N+2)]
for v in range(N): E[v][v] = 0
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    E[i][j] = E[j][i] = d
dist = [float('inf')] * N # the distance of each vertex from s
prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
visited = [False] * N
n_visited = 0 # #(visited vertices)
heap = []
heappush(heap, (0, -1, 0))
while heap:
    d, p, v = heappop(heap)
    if visited[v]: continue # (s,v)-shortest path is already calculated
    dist[v] = d; prev[v] = p; visited[v] = True
    n_visited += 1
    if n_visited == N: break
    for u in range(N):
        if visited[u]: continue
        temp = d + E[v][u]
        if dist[u] > temp: heappush(heap, (temp, v, u))
print(dist[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Buggy python submission (verdict: Runtime Error):
from itertools import combinations
from heapq import heappush, heappop

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
E = [[float('inf')] * N for _ in range(N+2)]
for v in range(N): E[v][v] = 0
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    E[i][j] = E[j][i] = d
dist = [float('inf')] * N # the distance of each vertex from s
prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
visited = [False] * N
n_visited = 0 # #(visited vertices)
heap = []
heappush(heap, (0, -1, 0))
while heap:
    d, p, v = heappop(heap)
    if visited[v]: continue # (s,v)-shortest path is already calculated
    dist[v] = d; prev[v] = p; visited[v] = True
    n_visited += 1
    if n_visited == N: break
    for u in range(N):
        if visited[u]: continue
        temp = d + E[v][u]
        if dist[u] > temp: heappush(heap, (temp, v, u))
print(dist[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Buggy python submission (verdict: Runtime Error):
from itertools import combinations
from heapq import heappush, heappop

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
E = [[float('inf')] * N for _ in range(N)]
for v in range(N): E[v][v] = 0
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    E[i][j] = E[j][i] = d
dist = [float('inf')] * N # the distance of each vertex from s
prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
visited = [False] * N
n_visited = 0 # #(visited vertices)
heap = []
heappush(heap, (0, -1, 0))
while heap:
    d, p, v = heappop(heap)
    if visited[v]: continue # (s,v)-shortest path is already calculated
    dist[v] = d; prev[v] = p; visited[v] = True
    n_visited += 1
    if n_visited == N: break
    for u in range(N):
        if visited[u]: continue
        temp = d + E[v][u]
        if dist[u] > temp: heappush(heap, (temp, v, u))
print(dist[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

class DijkstraDense:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[float('inf')] * N for _ in range(N)]
        for v in range(N): self.E[v][v] = 0

    def add_edge(self, init, end, weight, undirected=False):
        if undirected: self.E[init][end] = self.E[end][init] = weight
        else: self.E[init][end] = weight
        
    def distance(self, s):
        E, N = self.E, self.N
        dist = [float('inf')] * N # the distance of each vertex from s
        prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        visited = [False] * N
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if visited[v]: continue # (s,v)-shortest path is already calculated
            dist[v] = d; prev[v] = p; visited[v] = True
            n_visited += 1
            if n_visited == N: break
            for u in range(N):
                if visited[u]: continue
                temp = d + E[v][u]
                if dist[u] > temp: heappush(heap, (temp, v, u))
        self.dist, self.prev = dist, prev
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = DijkstraDense(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

class DijkstraDense:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[float('inf')] * N for _ in range(N)]
        for v in range(N): self.E[v][v] = 0

    def add_edge(self, init, end, weight, undirected=False):
        if undirected: self.E[init][end] = self.E[end][init] = weight
        else: self.E[init][end] = weight
        
    def distance(self, s):
        E, N = self.E, self.N
        dist = [float('inf')] * N # the distance of each vertex from s
        prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        visited = [False] * N
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if visited[v]: continue # (s,v)-shortest path is already calculated
            dist[v] = d; prev[v] = p; visited[v] = True
            n_visited += 1
            if n_visited == N: break
            for u in range(N):
                if visited[u]: continue
                temp = d + E[v][u]
                if dist[u] > temp: heappush(heap, (temp, v, u))
        self.dist, self.prev = dist, prev
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = DijkstraDense(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        E, N = self.E, self.N
        dist = [float('inf')] * N # the distance of each vertex from s
        prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        visited = [False] * N
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if visited[v]: continue # (s,v)-shortest path is already calculated
            dist[v] = d; prev[v] = p; visited[v] = True
            n_visited += 1
            if n_visited == N: break
            for u, c in E[v]:
                if visited[u]: continue
                temp = d + c
                if dist[u] > temp: heappush(heap, (temp, v, u))
        self.dist, self.prev = dist, prev
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]
    
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):
    x, y, r = map(int, input().split())
    P.append([(x, y), r])
dk = Dijkstra(N+2)
E = [[] for _ in range(N+2)]
for i, j in combinations(range(N+2), 2):
    p1, r1 = P[i]; p2, r2 = P[j]
    temp = ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5 - (r1 + r2)
    d = temp if temp > 0 else 0
    E[i].append((j, d)); E[j].append((i, d))
dk.E = E
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        E, N = self.E, self.N
        dist = [float('inf')] * N # the distance of each vertex from s
        prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        visited = [False] * N
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if visited[v]: continue # (s,v)-shortest path is already calculated
            dist[v] = d; prev[v] = p; visited[v] = True
            n_visited += 1
            if n_visited == N: break
            for u, c in E[v]:
                if visited[u]: continue
                temp = d + c
                if dist[u] > temp: heappush(heap, (temp, v, u))
        self.dist, self.prev = dist, prev
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]
    
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):
    x, y, r = map(int, input().split())
    P.append([(x, y), r])
dk = Dijkstra(N+2)
for i, j in combinations(range(N+2), 2):
    p1, r1 = P[i]; p2, r2 = P[j]
    temp = ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5 - (r1 + r2)
    d = temp if temp > 0 else 0
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        E, N = self.E, self.N
        dist = [float('inf')] * N # the distance of each vertex from s
        prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        visited = [False] * N
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if visited[v]: continue # (s,v)-shortest path is already calculated
            dist[v] = d; prev[v] = p; visited[v] = True
            n_visited += 1
            if n_visited == N: break
            for u, c in E[v]:
                if visited[u]: continue
                temp = d + c
                if dist[u] > temp: heappush(heap, (temp, v, u))
        self.dist, self.prev = dist, prev
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    temp = ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5 - (r1 + r2)
    d = temp if temp > 0 else 0
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        E, N = self.E, self.N
        dist = [float('inf')] * N # the distance of each vertex from s
        prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        visited = [False] * N
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if visited[v]: continue # (s,v)-shortest path is already calculated
            dist[v] = d; prev[v] = p; visited[v] = True
            n_visited += 1
            if n_visited == N: break
            for u, c in E[v]:
                if visited[u]: continue
                temp = d + c
                if dist[u] > temp: heappush(heap, (temp, v, u))
        self.dist, self.prev = dist, prev
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
add = dk.add_edge
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    temp = dist(p1, p2) - (r1 + r2)
    d = temp if temp > 0 else 0
    add(i, j, d, undirected=True)
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        dist = [INF] * N # the distance of each vertex from s
        prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        visited = [False] * N
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if visited[v]: continue # (s,v)-shortest path is already calculated
            dist[v] = d; prev[v] = p; visited[v] = True
            n_visited += 1
            if n_visited == N: break
            for u, c in E[v]:
                if visited[u]: continue
                temp = d + c
                if dist[u] > temp: heappush(heap, (temp, v, u))
        self.dist, self.prev = dist, prev
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    temp = dist(p1, p2) - (r1 + r2)
    d = temp if temp > 0 else 0
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if dist[v] != INF: continue # (s,v)-shortest path is already calculated
            dist[v] = d; prev[v] = p
            n_visited += 1
            if n_visited == N: break
            for u, c in E[v]:
                if dist[u] != INF: continue
                temp = d + c
                if dist[u] > temp: heappush(heap, (temp, v, u))
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2):
    return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if dist[v] != INF: continue # (s,v)-shortest path is already calculated
            dist[v] = d; prev[v] = p
            n_visited += 1
            if n_visited == N: break
            for u, c in E[v]:
                if dist[u] != INF: continue
                temp = d + c
                if dist[u] > temp: heappush(heap, (temp, v, u))
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2):
    return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

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

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        self.dist = [INF] * self.N # the distance of each vertex from s
        self.prev = [-1] * self.N # the previous vertex of each vertex on a shortest path from s
        n_visited = 0 # #(visited vertices)
        heap = []
        heappush(heap, (0, -1, s))
        while heap:
            d, p, v = heappop(heap)
            if self.dist[v] != INF: continue # (s,v)-shortest path is already calculated
            self.dist[v] = d; self.prev[v] = p
            n_visited += 1
            if n_visited == self.N: break
            for u, c in self.E[v]:
                if self.dist[u] != INF: continue
                temp = d + c
                if self.dist[u] > temp: heappush(heap, (temp, v, u))
        return self.dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2):
    return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])

Fixed submission:
from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])