Buggy python submission (verdict: Time Limit Exceeded):
from math import sqrt
import heapq

def calc(arr, i, j):
    d = sqrt((arr[i][0] - arr[j][0])**2 + (arr[i][1] - arr[j][1])**2)
    if arr[i][2] + arr[j][2] <= d:
        return d - arr[i][2] - arr[j][2]
    else:
        return 0

def main():
    xs, ys, xt, yt = map(int, input().split())
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    arr.append([xs, ys, 0])
    arr.append([xt, yt, 0])
    n += 2
    st = set()
    for i in range(n):
        st.add(i)
    dist = [float("inf")]*n
    dist[n-2] = 0
    dist[n-1] = calc(arr, n-2, n-1)
    hq = []
    heapq.heappush(hq, [0, n-2])
    while len(hq) > 0:
        _, p = heapq.heappop(hq)
        if p in st:
            st.remove(p)
            for nxt in st:
                d = calc(arr, p, nxt)
                if dist[nxt] > dist[p] + d:
                    dist[nxt] = dist[p] + d
                    heapq.heappush(hq, [dist[nxt], nxt])
    print(dist[-1])

if __name__ == "__main__":
    main()


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop,heappush
from math import sqrt
def dist(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  todo=[[0,n]]
  mi=set(range(n+2))
  seen=[float('inf')]*(n+2)
  seen[n]=0
  while todo:
    _,v=heappop(todo)
    if v not in mi:continue
    mi.remove(v)
    for nv in mi:
      nd=dist(xyr,v,nv)
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
        heappush(todo,[seen[nv],nv])
  print(seen[n+1])
if __name__=='__main__':
  main()


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def dist(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  from heapq import heappop,heappush
  todo=[[0,n]]
  mi=set(range(n+2))
  seen=[float('inf')]*(n+2)
  seen[n]=0
  while todo:
    _,v=heappop(todo)
    if v not in mi:continue
    mi.remove(v)
    for nv in mi:
      nd=dist(xyr,v,nv)
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
        heappush(todo,[seen[nv],nv])
  print(seen[n+1])
if __name__=='__main__':
  main()


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def dist(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  from heapq import heappop,heappush
  todo=[[0,n]]
  ka=set(())
  seen=[float('inf')]*(n+2)
  seen[n]=0
  while todo:
    _,v=heappop(todo)
    if v in ka:continue
    if v==n+1:
      print(seen[v])
      exit()
    ka.add(v)
    for nv in range(n+2):
      if v==nv or nv in ka:continue
      nd=dist(xyr,v,nv)
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
        heappush(todo,[seen[nv],nv])
if __name__=='__main__':
  main()


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  def dist(xyr,i,j):
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    return d
  from heapq import heappop,heappush
  todo=[[0,n]]
  ka=set(())
  seen=[float('inf')]*(n+2)
  seen[n]=0
  while todo:
    _,v=heappop(todo)
    if v in ka:continue
    if v==n+1:
      print(seen[v])
      exit()
    ka.add(v)
    for nv in range(n+2):
      if v==nv or nv in ka:continue
      nd=dist(xyr,v,nv)
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
        heappush(todo,[seen[nv],nv])
if __name__=='__main__':
  main()


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  def dist(xyr,i,j):
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    return d
  from heapq import heappop,heappush
  todo=[[0,n]]
  ka=set(())
  seen=[float('inf')]*(n+2)
  seen[n]=0
  while todo:
    d,v=heappop(todo)
    if v in ka:continue
    if v==n+1:
      print(d)
      exit()
    ka.add(v)
    for nv in range(n+2):
      if v==nv or nv in ka:continue
      nd=dist(xyr,v,nv)
      if seen[nv]>d+nd:
        heappush(todo,[d+nd,nv])
        seen[nv]=d+nd
if __name__=='__main__':
  main()


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  n+=2
  def dist(xyr,i,j):
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    return d
  from heapq import heappop,heappush
  todo=[[0,n-2]]
  ka=set(())
  seen=[float('inf')]*n
  seen[n-2]=0
  while todo:
    d,v=heappop(todo)
    if v in ka:continue
    if v==n-1:
      print(d)
      exit()
    ka.add(v)
    for nv in range(n):
      if nv in ka:continue
      nd=dist(xyr,v,nv)
      if seen[nv]>d+nd:
        heappush(todo,[d+nd,nv])
        seen[nv]=d+nd
if __name__=='__main__':
  main()


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[[xs,ys,0],[xt,yt,0]]
  xyr+=[list(map(int,input().split())) for _ in range(n)]
  memo={}
  def dist(xyr,i,j):
    if i<j:
      i,j=j,i
    if (i,j) in memo:return memo[(i,j)]
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    memo[(i,j)]=d
    return d
  from heapq import heappop,heappush
  todo=[[0,0]]
  ka=set(())
  seen=[-1]*(n+2)
  seen[0]=0
  while todo:
    d,v=heappop(todo)
    if v in ka:continue
    if v==1:
      print(d)
      exit()
    ka.add(v)
    for nv in range(n+2):
      if v==nv or nv in ka:continue
      nd=dist(xyr,v,nv)
      if seen[nv]==-1 or seen[nv]>d+nd:
        heappush(todo,[d+nd,nv])
        seen[nv]=d+nd
if __name__=='__main__':
  main()


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[[xs,ys,0],[xt,yt,0]]
  xyr+=[list(map(int,input().split())) for _ in range(n)]
  memo={}
  def dist(i,j):
    if i<j:
      i,j=j,i
    if (i,j) in memo:return memo[(i,j)]
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    memo[(i,j)]=d
    return d
  from heapq import heappop,heappush
  todo=[[0,0]]
  ka=set(())
  seen=[-1]*(n+2)
  seen[0]=0
  while todo:
    d,v=heappop(todo)
    if v in ka:continue
    if v==1:
      print(d)
      exit()
    ka.add(v)
    for nv in range(n+2):
      if v==nv or nv in ka:continue
      nd=dist(v,nv)
      if seen[nv]==-1 or seen[nv]>d+nd:
        heappush(todo,[d+nd,nv])
        seen[nv]=d+nd
if __name__=='__main__':
  main()


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[[xs,ys,0],[xt,yt,0]]
  xyr+=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n+2)]
  for i in range(n+1):
    for j in range(i+1,n+2):
      x,y,r=xyr[i]
      x1,y1,r1=xyr[j]
      d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
      g[i].append([d,j])
      g[j].append([d,i])
  xry=[]
  from heapq import heappop,heappush
  todo=[[0,0]]
  ka=set(())
  seen=[-1]*(n+2)
  seen[0]=0
  while todo:
    d,v=heappop(todo)
    if v in ka:continue
    if v==1:
      print(d)
      exit()
    ka.add(v)
    for nd,nv in g[v]:
      if seen[nv]==-1 or seen[nv]>d+nd:
        heappush(todo,[d+nd,nv])
        seen[nv]=d+nd
if __name__=='__main__':
  main()


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[[xs,ys,0],[xt,yt,0]]
xyr+=[list(map(int,input().split())) for _ in range(n)]
g=[[]for _ in range(n+2)]
for i in range(n+1):
  for j in range(i+1,n+2):
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    g[i].append([d,j])
    g[j].append([d,i])
xry=[]
from heapq import heappop,heappush
todo=[[0,0]]
ka=set(())
seen=[-1]*(n+2)
seen[0]=0
while todo:
  d,v=heappop(todo)
  if v in ka:continue
  if v==1:
    print(d)
    exit()
  ka.add(v)
  for nd,nv in g[v]:
    if seen[nv]==-1 or seen[nv]>d+nd:
      heappush(todo,[d+nd,nv])
      seen[nv]=d+nd


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[[xs,ys,0],[xt,yt,0]]
xyr+=[list(map(int,input().split())) for _ in range(n)]
g=[[]for _ in range(n+2)]
for i in range(n+2):
  for j in range(n+2):
    if i==j:continue
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    g[i].append([d,j])
    g[j].append([d,i])
from heapq import heappop,heappush
todo=[[0,0]]
ka=set(())
seen=[-1]*(n+2)
seen[0]=0
while todo:
  d,v=heappop(todo)
  if v in ka:continue
  if v==1:
    print(d)
    exit()
  ka.add(v)
  for nd,nv in g[v]:
    if seen[nv]==-1 or seen[nv]>d+nd:
      heappush(todo,[d+nd,nv])
      seen[nv]=d+nd


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
xs,ys,xt,yt=map(int,input().split())
n=int(input())
xyr=[[xs,ys,0],[xt,yt,0]]
xyr+=[list(map(int,input().split())) for _ in range(n)]
g=[[]for _ in range(n+2)]
for i in range(n+2):
  for j in range(n+2):
    if i==j:continue
    x,y,r=xyr[i]
    x1,y1,r1=xyr[j]
    d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
    g[i].append([d,j])
    g[j].append([d,i])
from heapq import heappop,heappush
todo=[[0,0]]
ka=set(())
seen=[-1]*(n+2)
seen[0]=0
while todo:
  d,v=heappop(todo)
  if v in ka:continue
  if v==1:
    print(d)
    exit()
  ka.add(v)
  for nd,nv in g[v]:
    if seen[nv]==-1 or seen[nv]>d+nd:
      heappush(todo,[d+nd,nv])
      seen[nv]=d+nd


Fixed submission:
from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()