Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
import heapq
def dijkstra(x,route):
    n=len(route)
    d=[float('inf')]*n
    d[x]=0
    Visited=[False]*n
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        Visited[u]=True
        for v,cost in route[u]:
            if (not Visited[v]) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+1):
    for j in range(i+1,n+2):
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
        Edges[j].append((i,d))
print(dijkstra(0,Edges)[-1])

Fixed submission:
import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
import heapq
def dijkstra(x,route):
    n=len(route)
    d=[float('inf')]*n
    d[x]=0
    Visited=[False]*n
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        Visited[u]=True
        for v,cost in route[u]:
            if (not Visited[v]) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

def main():
    sx,sy,gx,gy=map(int,input().split())
    n=int(input())
    V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
    Edges=[[] for _ in range(n+2)]
    for i in range(n+1):
        for j in range(i,n+2):
            d=dist(V[i],V[j])
            Edges[i].append((j,d))
            Edges[j].append((i,d))
    print(dijkstra(0,Edges)[-1])

if __name__=='__main__':
    main()

Fixed submission:
import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def dijkstra(x,route):
    n=len(route)
    d=[10**10]*n
    d[x]=0
    Visited=[False]*n
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        Visited[u]=True
        for v,cost in route[u]:
            if (not Visited[v]) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

import sys
input=sys.stdin.readline
sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
        Edges[j].append((i,d))
print(dijkstra(0,Edges)[-1])

Fixed submission:
import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def dijkstra(x,route):
    n=len(route)
    d=[float('inf')]*n
    d[x]=0
    Visited=[False]*n
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        Visited[u]=True
        for v,cost in route[u]:
            if (not Visited[v]) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    dx=V2[0]-V1[0]; dy=V2[1]-V1[1]
    sum_r=V1[2]+V2[2]
    return max(0,(dx**2+dy**2)**0.5-sum_r)

import sys
input=sys.stdin.readline
sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
        Edges[j].append((i,d))
print(dijkstra(0,Edges)[-1])

Fixed submission:
import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def dijkstra(x,route):
    n=len(route)
    d=[float('inf')]*n
    d[x]=0
    Visited=[False]*n
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        Visited[u]=True
        for v,cost in route[u]:
            if (not Visited[v]) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    dx=V2[0]-V1[0]; dy=V2[1]-V1[1]
    sum_r=V1[2]+V2[2]
    return max(0,(dx**2+dy**2)**0.5-sum_r)

import sys
input=sys.stdin.readline
sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+2):
    for j in range(n+2):
        if i==j:
            continue
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
print(dijkstra(0,Edges)[-1])

Fixed submission:
import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def dijkstra(x,route):
    n=len(route)
    d=[float('inf')]*n
    d[x]=0
    visited={x}
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        visited.add(u)
        for v,cost in route[u]:
            if (v not in visited) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    dx=V2[0]-V1[0]; dy=V2[1]-V1[1]
    sum_r=V1[2]+V2[2]
    return max(0,(dx**2+dy**2)**0.5-sum_r)

import sys
input=sys.stdin.readline
sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+2):
    for j in range(n+2):
        if i==j:
            continue
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
print(dijkstra(0,Edges)[-1])

Fixed submission:
import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def dijkstra(x,route):
    n=len(route)
    d=[float('inf')]*n
    d[x]=0
    visited={x}
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        visited.add(u)
        for v,cost in route[u]:
            if (v not in visited) and d[v]>d[u]+cost:
                d[v]=d[u]+cost
                heapq.heappush(hq,(d[v],v))
    return d

def dist(V1,V2):
    dx=V2[0]-V1[0]; dy=V2[1]-V1[1]
    sum_r=V1[2]+V2[2]
    return max(0,(dx**2+dy**2)**0.5-sum_r)

import sys
input=sys.stdin.readline
sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Edges=[[] for _ in range(n+2)]
for i in range(n+2):
    for j in range(n+2):
        if i==j:
            continue
        d=dist(V[i],V[j])
        Edges[i].append((j,d))
print(dijkstra(0,Edges)[-1])

Fixed submission:
import sys
input=sys.stdin.readline

def dijkstra(s,n,Cost):
    D=[float('inf')]*n
    Visited=[False]*n
    D[s]=0
    while True:
        v=-1
        for i in range(n):
            if (not Visited[i]) and v==-1:
                v=i
            elif (not Visited[i]) and D[i]<D[v]:
                v=i
        if v==-1:
            break
        Visited[v]=True
        for j in range(n):
            D[j]=min(D[j],D[v]+Cost[v][j])
    return D

def dist(V1,V2):
    return max(0,((V2[0]-V1[0])**2+(V2[1]-V1[1])**2)**0.5-(V1[2]+V2[2]))

sx,sy,gx,gy=map(int,input().split())
n=int(input())
V=[(sx,sy,0)]+[tuple(map(int,input().split())) for _ in range(n)]+[(gx,gy,0)]
Cost=[[float('inf')]*(n+2)for _ in range(n+2)]
for i in range(n+1):
    for j in range(i,n+2):
        d=dist(V[i],V[j])
        Cost[i][j]=d; Cost[j][i]=d
print(dijkstra(0,n+2,Cost)[-1])