Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    d = [list(map(int, input().split())) for _ in range(n)]

    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            flag = True
            for k in range(n):
                if k == i or k == j:
                    continue
                if d[i][j] > d[i][k]+d[k][j]:
                    print(-1)
                    exit()
                elif d[i][j] == d[i][k]+d[k][j]:
                    flag = False
                else:
                    pass
            if flag:
                ans += d[i][j]
    #print(ans)
    print(ans//2)

if __name__ == '__main__':
    main()


Fixed submission:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

import copy
B = copy.deepcopy(A)
B = warshal_floyd(B)

ans = 0
for i in range(n):
    for j in range(n):
        if B[i][j] < A[i][j]:
            print(-1)
            exit()
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if B[i][j] == B[i][k] + B[k][j]:
                    break
            else:
                ans += A[i][j]
ans //=2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

import copy
B = copy.deepcopy(A)
B = warshal_floyd(B)

ans = 0
for i in range(n):
    for j in range(n):
        if B[i][j] < A[i][j]:
            print(-1)
            exit()
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if B[i][j] == B[i][k] + B[k][j]:
                    break
            else:
                ans += A[i][j]
ans //=2
print(ans)

Fixed submission:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

import copy
B = copy.deepcopy(A)
B = warshal_floyd(B)

ans = 0
for i in range(n):
    for j in range(n):
        if B[i][j] < A[i][j]:
            print(-1)
            exit()
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if B[i][j] == B[i][k] + B[k][j]:
                    break
            else:
                ans += A[i][j]
ans //=2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

n, m, r = map(int, input().split())
R = list(map(int, input().split()))
R = [r_-1 for r_ in R]

d = [[float('inf') for i in range(n)] for j in range(n)]

for i in range(m):
  x, y, z = map(int, input().split())
  x, y = x-1, y-1
  d[x][y] = z
  d[y][x] = z
  
for i in range(n):
  d[i][i] = 0

d = warshal_floyd(d)

import itertools
ans = float('inf')
for p in itertools.permutations(R):
  q = 0
  for i in range(len(p)-1):
    q += d[p[i]][p[i+1]]
  if q <= ans:
    ans = q
print(ans)

Fixed submission:
def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

n, m, r = map(int, input().split())
R = list(map(int, input().split()))
R = [r_-1 for r_ in R]

d = [[float('inf') for i in range(n)] for j in range(n)]

for i in range(m):
  x, y, z = map(int, input().split())
  x, y = x-1, y-1
  d[x][y] = z
  d[y][x] = z
  
for i in range(n):
  d[i][i] = 0

d = warshal_floyd(d)

import itertools
ans = float('inf')
for p in itertools.permutations(R):
  q = 0
  for i in range(len(p)-1):
    q += d[p[i]][p[i+1]]
  if q <= ans:
    ans = q
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
A = list(map(int, input().split()))
A.sort()
#print(A)

d = {}
for i in range(n):
    a = A[i]
    for k in (-1, 0, 1):
        if a+k not in d:
            d[a+k] = 1
        else:
            d[a] += 1
max_ = 0
for v in d.values():
    if v >= max_:
        max_ = v
print(max_)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

d = {}

for i in range(max(a)+1):
  d[i] = 0

for a_ in a:
  d[a_] += 1

d[-1] = 0
d[max(a)+1] = 0

ans = 0

for x in range(max(a)+1):
  if x-1 in d:
    ans = max(ans, d[x-1] + d[x] + d[x+1])

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

ys = [0] * (max(a)+ 1)

for x in range(len(ys)):
    y = a.count(x-1) + a.count(x) + a.count(x+1)
    ys[x] = y

print(max(ys))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

d = {}

for i in range(max(a)+1):
  d[i] = 0

for a_ in a:
  d[a_] += 1

d[-1] = 0
d[max(a)+1] = 0

ans = 0

for x in range(max(a)+1):
  if x-1 in d:
    ans = max(ans, d[x-1] + d[x] + d[x+1])

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

ys = [0] * (max(a)+ 1)

for x in range(len(ys)):
    y = a.count(x-1) + a.count(x) + a.count(x+1)
    ys[x] = y

print(max(ys))
    

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

d = {}

for i in range(max(a)+1):
  d[i] = 0

for a_ in a:
  d[a_] += 1

d[-1] = 0
d[max(a)+1] = 0

ans = 0

for x in range(max(a)+1):
  if x-1 in d:
    ans = max(ans, d[x-1] + d[x] + d[x+1])

print(ans)
Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

def lcm_base(x, y):
  return (x*y)//math.gcd(x, y)

def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)

n = int(input())
ts = [0]*n
for i in range(n):
  ts[i] = int(input())

print(lcm_list(ts))

Fixed submission:
import fractions
from functools import reduce
 
def lcm_base(x, y):
  return (x*y)//fractions.gcd(x, y)
 
def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)
 
n = int(input())
ts = [0]*n
for i in range(n):
  ts[i] = int(input())

print(lcm_list(ts))
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
n = int(input())
l = list(map(int, input().split()))

ans = []
for i in range(n):
  ans += [i+1]*l[i]

for i in range(h):
  temp = ans[i*w:(i+1)*w]
  if i%2 == 0:
    print(*temp)
  else:
    temp = reversed(temp)
    print(*temp)

Fixed submission:
n, m = map(int, input().split())
print((n-1)*(m-1))
Buggy python submission (verdict: Runtime Error):
w = map(int, input().split())
n = int(input())
l = list(map(int, input().split()))
 
ans = []
for i in range(n):
  ans += [i+1]*l[i]
 
for i in range(h):
  temp = ans[i*w:(i+1)*w]
  if i%2 == 0:
    print(*temp)
  else:
    temp = reversed(temp)
    print(*temp)

Fixed submission:
h, w = map(int, input().split())
n = int(input())
l = list(map(int, input().split()))

ans = []
for i in range(n):
  ans += [i+1]*l[i]

for i in range(h):
  temp = ans[i*w:(i+1)*w]
  if i%2 == 0:
    print(*temp)
  else:
    temp = reversed(temp)
    print(*temp)
Buggy python submission (verdict: Runtime Error):
k = int(input())
n = k+1

A = [0]*n
A[0] = (n-1)+n*k
print(n)
print(*A)


Fixed submission:
k = int(input())
n = 50

q, r = divmod(k, n)
A = [n-1]*n
for i in range(n):
    A[i] += q

for i in range(r):
    A[i] += n+1
    for j in range(n):
        A[j] -= 1

print(n)
print(*A)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
print(l[0]+l[1]+l[2])

Fixed submission:
n, k = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
ans = 0
for i in range(k):
  ans +=l[i]
print(ans)
Buggy python submission (verdict: Runtime Error):
a, b, c = map(int, input().split())
print(min([a+b, b+c, c+a])

Fixed submission:
a, b, c = map(int, input().split())
print(min([a+b, b+c, c+a]))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
  ai = a[i]
  b.append(ai)
  b.reverse()
print(' '.join(map(str, b)))

Fixed submission:
from collections import deque

n = int(input())
a = list(map(int, input().split()))

b = deque()

if n%2 == 0:
  for i in range(n):
    ai = a[i]
    if i%2 == 0:
      b.append(ai)
    else:
      b.appendleft(ai)
else:
  for i in range(n):
    ai = a[i]
    if i%2 == 0:
      b.appendleft(ai)
    else:
      b.append(ai)
print(' '.join(map(str, b)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
  ai = a[i]
  b.append(ai)
  b.reverse()
print(' '.join(map(str, b)))

Fixed submission:
from collections import deque

n = int(input())
a = list(map(int, input().split()))

b = deque()

if n%2 == 0:
  for i in range(n):
    ai = a[i]
    if i%2 == 0:
      b.append(ai)
    else:
      b.appendleft(ai)
else:
  for i in range(n):
    ai = a[i]
    if i%2 == 0:
      b.appendleft(ai)
    else:
      b.append(ai)
print(' '.join(map(str, b)))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

import heapq
n = int(input())
l = [[0, 0] for i in range(n)]
for i in range(n):
  x, y = map(int, input().split())
  l[i][0] = x
  l[i][1] = y
  
graph = []
for i in range(n-1):
  x1, y1 = l[i]
  for j in range(i, n):
    x2, y2 = l[j]
    graph.append((min(abs(x1-x2), abs(y1-y2)), i, j))
    graph.append((min(abs(x1-x2), abs(y1-y2)), j, i))

#union find
def Find(x, par):
  if par[x] < 0:
    return x
  else:
    # 経路圧縮
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)
  
  if x != y:
    # rankの低い方を高い方につなげる
    if rank[x] < rank[y]:
      par[y] += par[x]
      par[x] = y
    else:
      par[x] += par[y]
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1
    
def Same(x, y, par):
  return Find(x, par) == Find(y, par)
 
def Size(x, par):
  return -par[Find(x)]

#print(graph)
graph.sort()
par = [-1]*n
rank = [0]*n

cost = 0

for d, p, q in graph:
  if not Same(p, q, par):
    cost += d
    Unite(p, q, par, rank)

print(cost)

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

n = int(input())
P = []
for i in range(n):
    x, y = map(int, input().split())
    P.append((x, y, i))

import heapq
def prim_heap():
    used = [True]*n
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist, e)
        used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not  used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, e)
        res += minedge[0]
    return res

P.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))

P.sort(key = lambda x: x[1])
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))

print(prim_heap())
Buggy python submission (verdict: Runtime Error):
def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

n, m, p = map(int, input().split())
print(power(n, p, m))

Fixed submission:
n = int(input())
s = str(input())
A = [0]
cum = 0
ans = ''
for i in range(n):
    if s[i] == '(':
        cum += 1
    else:
        cum -= 1
    if cum == -1:
        ans = '('+ans
        ans += s[i]
        cum = 0
    else:
        ans += s[i]
else:
    if cum > 0:
        ans += ')'*cum
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
AB = []
for i in range(n):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort()
cnt = 0
X = []
for i in range(n):
    a, b = AB[i]
    X += [a]*b
    cnt += b
    if cnt > k:
        break
X.sort()
print(X[k-1])


Fixed submission:
n, k = map(int, input().split())

ab = [[0, 0] for _ in range(n)]

for i in range(n):
  a, b = map(int, input().split())
  ab[i][0] = a
  ab[i][1] = b

ab.sort()
s = 0
i = 0
while s< k:
  s += ab[i][1]
  ans = ab[i][0]
  i += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
L = list(map(int, input().split()))
if L[0]%2 == 1 or L[1]%2 == 1 or L[2]%2 == 1:
    print(0)
    exit()

if (L[0]//2)%2 == 1 and (L[1]//2)%2 == 1 and (L[2]//2)%2 == 1:
    print(-1)
    exit()

i = 0
while True:
    i += 1
    L = [L[1]//2+L[2]//2, L[0]//2+L[2]//2, L[0]//2+L[1]//2]
    if L[0]%2 == 1 or L[1]%2 == 1 or L[2]%2 == 1:
        print(i)
        exit()


Fixed submission:
L = list(map(int, input().split()))
if L[0]%2 == 1 or L[1]%2 == 1 or L[2]%2 == 1:
    print(0)
    exit()

if (L[0]//2)%2 == 1 and (L[1]//2)%2 == 1 and (L[2]//2)%2 == 1:
    print(-1)
    exit()

i = 0
while True:
    i += 1
    L = [L[1]//2+L[2]//2, L[0]//2+L[2]//2, L[0]//2+L[1]//2]
    if L[0]%2 == 1 or L[1]%2 == 1 or L[2]%2 == 1:
        print(i)
        exit()
    if i >= 10**6:
        print(-1)
        exit()
Buggy python submission (verdict: Runtime Error):
import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
d = {}
for i in range(n):
    d[i] = 0

for i in range(n):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    d[a] += 1
    d[b] += 1

for v in d.values():
    if v%2 != 0:
        print('NO')
        exit()
else:
    print('YES')

Fixed submission:
import sys
#sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
d = {}
for i in range(n):
    d[i] = 0

for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    d[a] += 1
    d[b] += 1

for v in d.values():
    if v%2 != 0:
        print('NO')
        exit()
else:
    print('YES')
Buggy python submission (verdict: Runtime Error):
a, b, c = map(int, input())
if (b-a) == (c-b):
  print('YES')
else:
  print('NO')

Fixed submission:
a, b, c = map(int, input().split())
if (b-a) == (c-b):
  print('YES')
else:
  print('NO')
Buggy python submission (verdict: Runtime Error):
o = str(input())
e = str(input())

s = ''

for i in range(len(o)):
  s += o[i]
  s += e[i]

if len(o) == len(e) +1:
  s += o[-1]

print(s)

Fixed submission:
o = str(input())
e = str(input())

s = ''

for i in range(len(e)):
  s += o[i]
  s += e[i]

if len(o) == len(e) +1:
  s += o[-1]

print(s)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = str(input())

l = ['SS', 'SW', 'WS', 'WW']

for i in range(4):
  ans = l[i]
  for j in range(1, n):
    if ans[j] == 'S' and s[j] == 'o':
      if ans[j-1] == 'S':
        ans += 'S'
      else:
        ans += 'W'
    elif ans[j] == 'S' and s[j] == 'x':
      if ans[j-1] == 'S':
        ans += 'W'
      else:
        ans += 'S'
    elif ans[j] == 'W' and s[j] == 'o':
      if ans[j-1] == 'S':
        ans += 'W'
      else:
        ans += 'S'
    else:
      if ans[j-1] == 'S':
        ans += 'S'
      else:
        ans += 'W' 
  flag = 0
  if ans[-1] == ans[0]:
    if ans[0] == 'S' and s[0] == 'o':
      if ans[-2] == ans[1]:
        flag = 1
    elif ans[0] == 'W' and s[0] == 'o':
      if ans[-2] != ans[1]:
        flag = 1
    elif ans[0] == 'S' and s[0] == 'x':
      if ans[-2] != ans[1]:
        flag = 1
    else:
      if ans[-2] == ans[1]:
        flag = 1
  if flag == 1:
    print(ans[:-1])
    exit()
else:
  print('-1')

Fixed submission:
n = int(input())
s = str(input())

l = ['SS', 'SW', 'WS', 'WW']

for i in range(4):
  ans = l[i]
  for j in range(1, n):
    if ans[j] == 'S' and s[j] == 'o':
      if ans[j-1] == 'S':
        ans += 'S'
      else:
        ans += 'W'
    elif ans[j] == 'S' and s[j] == 'x':
      if ans[j-1] == 'S':
        ans += 'W'
      else:
        ans += 'S'
    elif ans[j] == 'W' and s[j] == 'o':
      if ans[j-1] == 'S':
        ans += 'W'
      else:
        ans += 'S'
    else:
      if ans[j-1] == 'S':
        ans += 'S'
      else:
        ans += 'W' 
  flag = 0
  if ans[-1] == ans[0]:
    if ans[0] == 'S' and s[0] == 'o':
      if ans[-2] == ans[1]:
        flag = 1
    elif ans[0] == 'W' and s[0] == 'o':
      if ans[-2] != ans[1]:
        flag = 1
    elif ans[0] == 'S' and s[0] == 'x':
      if ans[-2] != ans[1]:
        flag = 1
    else:
      if ans[-2] == ans[1]:
        flag = 1
  if flag == 1:
    print(ans[:-1])
    exit()
else:
  print('-1')
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, ma, mb = map(int, input().split())
    ABC = []
    for i in range(n):
        a, b, c = map(int, input().split())
        ABC.append((a, b, c))

    INF = 10**18
    dp = [[[INF]*405 for i in range(405)] for j in range(n+1)]
    dp[0][0][0] = 0
    for i in range(n):
        a, b, c = ABC[i]
        for j in range(405):
            for k in range(405):
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                nj, nk = j+a, k+b
                if 1 <= nj <= 404 and 1 <= nk <= 404:
                    dp[i+1][nj][nk] = min(dp[i][nj][nk], dp[i][j][k]+c)

    import fractions
    ans = INF
    for j in range(1, 405):
        for k in range(1, 405):
            if ma*k == mb*j:
                ans = min(ans, dp[n][j][k])
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n, ma, mb = map(int, input().split())
    ABC = []
    for i in range(n):
        a, b, c = map(int, input().split())
        ABC.append((a, b, c))

    INF = 10**18
    dp = [[[INF]*405 for i in range(405)] for j in range(n+1)]
    dp[0][0][0] = 0
    for i in range(n):
        a, b, c = ABC[i]
        for j in range(405):
            for k in range(405):
                dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
                nj, nk = j+a, k+b
                if 1 <= nj <= 404 and 1 <= nk <= 404:
                    dp[i+1][nj][nk] = min(dp[i][nj][nk], dp[i][j][k]+c)

    import fractions
    ans = INF
    for j in range(1, 405):
        for k in range(1, 405):
            if ma*k == mb*j:
                ans = min(ans, dp[n][j][k])
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ans +=1
print(ans)

Fixed submission:
k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= (s-x-y) <=k:
                ans +=1
print(ans)
Buggy python submission (verdict: Runtime Error):
I, O, T, J, L, S, Z = map(int, input().split())
k0 = 0
k0 += (I//2)*2
k0 += (J//2)*2
k0 += (L//2)*2

k1 = 0
if I >= 1 and J >= 1 and L >= 1:
    k1 = 0
    k += 3
    I -= 1
    J -= 1
    L -= 1
    k1 += (I//2)*2
    k1 += (J//2)*2
    k1 += (L//2)*2

k = max(k0, k1)
k += O
print(k)

Fixed submission:
I, O, T, J, L, S, Z = map(int, input().split())
k0 = 0
k0 += (I//2)*2
k0 += (J//2)*2
k0 += (L//2)*2

k1 = 0
if I >= 1 and J >= 1 and L >= 1:
    k1 = 0
    k1 += 3
    I -= 1
    J -= 1
    L -= 1
    k1 += (I//2)*2
    k1 += (J//2)*2
    k1 += (L//2)*2

k = max(k0, k1)
k += O
print(k)
Buggy python submission (verdict: Runtime Error):
a, op, b = map(int, input().split())
if op == '+':
  print(a+b)
else:
  print(a-b)

Fixed submission:
a, op, b = input().split()
a = int(a)
b = int(b)
op = str(op)

if op == '+':
  print(a+b)
else:
  print(a-b)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, x = map(int, input().split())
ans = 0
for i in range(a, b+1):
  if i%x == 0:
    ans += 1
print(ans)

Fixed submission:
a, b, x = map(int, input().split())
if a%x == 0 and b%x == 0:
  ans = b//x -a//x +1
elif a%x != 0 and b%x == 0:
  ans = b//x -a//x
elif a%x == 0 and b%x != 0:
  ans = b//x -a//x +1
else:
  ans = b//x -a//x
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
xs, ys, xt, yt = map(int, input().split())
n = int(input())
X = [[0, 0, 0] for _ in range(n+2)]
X[0] = [xs, ys, 0]
X[n+1] = [xt, yt, 0]
R = [0]*n
for i in range(n):
    x, y, r = map(int, input().split())
    X[i+1] = [x, y, r]

import math
edge = [[] for _ in range(n+2)]
for i in range(n+1):
    x1, y1, r1 = X[i]
    for j in range(i+1, n+2):
        x2, y2, r2 = X[j]
        l = math.sqrt((x1-x2)**2+(y1-y2)**2)
        edge[i].append((max(l-r1-r2, 0), j))
        edge[j].append((max(l-r1-r2, 0), i))

import heapq
def dijkstra_heap(s):
    d = [float("inf")] * (n+2)
    used = [True] * (n+2) #True: not used
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

d = dijkstra_heap(0)
print(d[-1])

Fixed submission:
xs, ys, xt, yt = map(int, input().split())
n = int(input())
X = [[0, 0, 0] for _ in range(n+2)]
X[0] = [xs, ys, 0]
X[n+1] = [xt, yt, 0]
R = [0]*n
for i in range(n):
    x, y, r = map(int, input().split())
    X[i+1] = [x, y, r]

import math
edge = [[] for _ in range(n+2)]
for i in range(n+1):
    x1, y1, r1 = X[i]
    for j in range(i+1, n+2):
        x2, y2, r2 = X[j]
        l = math.sqrt((x1-x2)**2+(y1-y2)**2)
        edge[i].append((max(l-r1-r2, 0), j))
        edge[j].append((max(l-r1-r2, 0), i))

import heapq
def dijkstra_heap(s):
    d = [float("inf")] * (n+2)
    used = [True] * (n+2) #True: not used
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d

d = dijkstra_heap(0)
print(d[-1])