Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15
from itertools import accumulate

def equal_l(cumsum,i):
    f = lambda j:abs(cumsum[i + 1] - 2*cumsum[j])
    l = 1
    r = i + 1
    while r - l > 1:
        mid = (l + r)//2
        if f(mid) - f(mid - 1) >= 0:
            r = mid
        else:
            l = mid
    #print('equeal_l:{0},{1}'.format(l,r))
    return cumsum[i + 1] - cumsum[l],cumsum[l]

def equal_r(cumsum,i,N):
    f = lambda j:abs(cumsum[-1] - cumsum[i + 1] - 2*(cumsum[j] - cumsum[i + 1]))
    l = i + 2
    r = N
    while r - l > 1:
        mid = (l + r)//2
        if f(mid) -  f(mid - 1) >= 0:
            r = mid
        else:
            l = mid
    #print('equeal_r:{0},{1}'.format(l,r))
    return  cumsum[-1] - cumsum[l],cumsum[l] - cumsum[i + 1]

def main():
    N = int(input())
    A = list(map(int,input().split()))
    cumsum = list(accumulate([0] + A))
    ans = INF
    for i in range(1,N - 2):
        a,b = equal_l(cumsum,i)
        c,d = equal_r(cumsum,i,N)
        ret = max(a,b,c,d) - min(a,b,c,d)
        ans = min(ans,ret)
    print(ans)
    
if __name__ == '__main__':
    main()
    


Fixed submission:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15
from itertools import accumulate

def equal_l(cumsum,i):
    f = lambda j:abs(cumsum[i + 1] - 2*cumsum[j])
    l = 1
    r = i + 1
    while r - l > 1:
        mid = (l + r)//2
        if f(mid) - f(mid - 1) >= 0:
            r = mid
        else:
            l = mid
    #print('equeal_l:{0},{1}'.format(l,r))
    return cumsum[i + 1] - cumsum[l],cumsum[l]

def equal_r(cumsum,i,N):
    f = lambda j:abs(cumsum[-1] - cumsum[i + 1] - 2*(cumsum[j] - cumsum[i + 1]))
    l = i + 2
    r = N
    while r - l > 1:
        mid = (l + r)//2
        if f(mid) -  f(mid - 1) >= 0:
            r = mid
        else:
            l = mid
    #print('equeal_r:{0},{1}'.format(l,r))
    return  cumsum[-1] - cumsum[l],cumsum[l] - cumsum[i + 1]

def main():
    N = int(input())
    A = list(map(int,input().split()))
    cumsum = list(accumulate([0] + A))
    ans = INF
    for i in range(1,N - 2):
        a,b = equal_l(cumsum,i)
        c,d = equal_r(cumsum,i,N)
        ret = max(a,b,c,d) - min(a,b,c,d)
        ans = min(ans,ret)
    print(ans)
    
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
grid=[list(input())  for i in range(h)]

dx=[-1,0,1,0]
dy=[0,1,0,-1]
for i in range(h):
    for j in range(w):
        if grid[i][j]=='#':
            flag=False
            for k in range(4):
                x=i+dx[k]
                y=j+dy[k]
                if 0<=x<w and 0<=y<h and grid[x][y]=='#':
                    flag=True
                    break
            if flag:
                continue
            else:
                print('No')
                exit()
print('Yes')

Fixed submission:
h,w=map(int,input().split())
grid=[list(input())  for i in range(h)]

dx=[-1,0,1,0]
dy=[0,1,0,-1]
for i in range(h):
    for j in range(w):
        if grid[i][j]=='#':
            flag=False
            for k in range(4):
                x=i+dx[k]
                y=j+dy[k]
                if 0<=x<h and 0<=y<w and grid[x][y]=='#':
                    flag=True
                    break
            if flag:
                continue
            else:
                print('No')
                exit()
print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
q=int(input())
a=[list(map(int,input().split())) for i in range(q)]

import math
def erato(n):
    prime=[]
    limit=math.sqrt(n)
    data=[i+1 for i in range(1,n)]
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]

tmp=max([a[i][1] for i in range(q)])+1
primes=erato(tmp)
#print(primes)
imos=[0]*(tmp)
for i in range(3,tmp):
    if i%2==1:
      if i in primes and (i+1)//2 in primes:
          imos[i]=imos[i-2]+1
      else:
          imos[i]=imos[i-2]
    if i%2==0:
      imos[i]=imos[i-1]
#print(imos)
for i in range(q):
    print(imos[a[i][1]]-imos[a[i][0]-1])


Fixed submission:
q=int(input())
M=100000

import math
def erato(n):
    prime=[]
    cnt=[0]*n
    limit=math.sqrt(n)
    data=[i+1 for i in range(1,n)]
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]

prime=erato(M)
cnt=[0]*M
for i in range(len(prime)):
  cnt[prime[i]]+=0.6
  if 2*prime[i]-1<M:
    cnt[2*prime[i]-1]+=0.6
 
for i in range(1,M):
  if cnt[i]>1:
    cnt[i]=cnt[i-1]//1+1
  else:
    cnt[i]=cnt[i-1]//1
    
#print(cnt)
for i in range(q):
  l,r=map(int,input().split())
  print(cnt[r]-cnt[l-1])
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100000000)

def main():
    S = input()
    N = len(S)
    ans = 0
    before = 0
    for i in range(N - 1):
        if S[i] != S[i + 1]:
            ans = max(ans,min(i + 1,N - before))
            before = i + 1
    ans = max(ans,min(i + 1,N - before))
    print(ans)
if __name__ == '__main__':
    main()

Fixed submission:
import sys
sys.setrecursionlimit(100000000)

def main():
    S = input()
    N = len(S)
    ans = 0
    before = 0
    for i in range(N - 1):
        if S[i] != S[i + 1]:
            ans = max(ans,min(N - before,i + 1))
            before = i + 1
    ans = max(ans,N - before)
    print(ans)
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

def dfs(i,j,p,z,w,a,n):
    if p == 0:
        if i == n:
            if j == 0:
                return abs(w - a[-1])
            return abs(a[j -1] - a[-1])
        ans = 0
        for k in range(i,n):
            ans = max(ans,dfs(k + 1,k,1,z,w,a,n))
        if i == 1:
            ans = max(ans,abs(a[-1] - w))
        else:
            ans = max(ans,abs(a[-1]- a[i - 1]))
        return ans
    elif p == 1:
        if i == n:
            if j == 0:
                return abs(z - a[-1])
            return abs(a[j - 1] - a[-1])
        ans = INF
        for k in range(i,n):
            ans = min(ans,dfs(k + 1,k,0,z,w,a,n))
        if i == 1:
            ans = min(ans,abs(a[-1] - z))
        else:
            ans = min(ans,abs(a[-1] - a[i - 1]))
        return ans

def main():
    n,z,w = map(int,input().split())
    a = list(map(int,input().split()))

    ans = dfs(1,0,0,z,w,a,n)
    print(ans)

if __name__=='__main__':
    main()

Fixed submission:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MAXN = 2005

dp0 = [[-1] * MAXN for _ in range(MAXN)]
dp1 = [[-1] * MAXN for _ in range(MAXN)]

def dfs(i,j,p,z,w,a,n):
    if p == 0:
        if dp0[i][j] != -1:
            return dp0[i][j]
        if i == n:
            if j == 0:
                return abs(w - a[-1])
            return abs(a[j -1] - a[-1])
        ans = 0
        for k in range(i,n):
            ans = max(ans,dfs(k + 1,k,1,z,w,a,n))
        if i == 1:
            ans = max(ans,abs(a[-1] - w))
        else:
            ans = max(ans,abs(a[-1]- a[i - 1]))
        dp0[i][j] = ans
        return ans
    elif p == 1:
        if dp1[i][j] != -1:
            return dp1[i][j]
        if i == n:
            if j == 0:
                return abs(z - a[-1])
            return abs(a[j - 1] - a[-1])
        ans = INF
        for k in range(i,n):
            ans = min(ans,dfs(k + 1,k,0,z,w,a,n))
        if i == 1:
            ans = min(ans,abs(a[-1] - z))
        else:
            ans = min(ans,abs(a[-1] - a[i - 1]))
        dp1[i][j] = ans
        return ans

def main():
    n,z,w = map(int,input().split())
    a = list(map(int,input().split()))

    ans = dfs(1,0,0,z,w,a,n)
    print(ans)

if __name__=='__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    if n%2 == 0:
        print(n//2,n,n)
        return
    for i in range(1,3501):
        for j in range(i + 1,3501):
            if (n * i * j)%(4 * i * j - n * j - n * i) == 0:
                ans = (i ,j , (n * i * j)//(4 * i * j - n * j - n * i))
                break
    
    print(*ans)

if __name__ =='__main__':
    main()  

Fixed submission:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    if n%2 == 0:
        print(n//2,n,n)
        return
    for i in range(1,3501):
        for j in range(i + 1,3501):
            if (n * i * j)%(4 * i * j - n * j - n * i) == 0:
                ans = (i ,j , (n * i * j)//(4 * i * j - n * j - n * i))
                break
    
    print(*ans)

if __name__ =='__main__':
    main()
Buggy python submission (verdict: Runtime Error):
INF = 10 ** 15
MOD = 10 ** 9 + 7 
from collections import deque

def main():
    N,K = map(int,input().split())
    number = [tuple(map(int,input().split())) for _ in range(N)]

    msb = 30
    while (K>>msb)&1 == 0:
        msb -= 1

    ans = 0
    for i in range(msb + 1):
        x = K >> i
        if i > 0:
            x -= 1
        ret = 0
        for a,b in number:
            if (a>>i) | x == x:
                ret += b
        ans = max(ans,ret)      
    print(ans)
if __name__ == '__main__':
    main()

Fixed submission:
INF = 10 ** 15
MOD = 10 ** 9 + 7 
from collections import deque

def main():
    N,K = map(int,input().split())
    number = [tuple(map(int,input().split())) for _ in range(N)]
    if K == 0:
        ans = 0
        for a,b in number:
            if a == 0:
                ans += b
        print(ans)
        return 

    msb = 30
    while (K>>msb)&1 == 0:
        msb -= 1

    ans = 0
    for i in range(msb + 1):
        x = K >> i
        if i > 0:
            x -= 1
        ret = 0
        for a,b in number:
            if (a>>i) | x == x:
                ret += b
        ans = max(ans,ret)      
    print(ans)
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys 
MOD = 10 ** 9 + 7
INF = 10**5
from collections import deque

def main():
    n = int(input())
    dist = []
    edge = []
    ans = 0
    for i in range(n):
        a = list(map(int,input().split()))
        dist.append(a)
        for j in range(n):
            if i < j:
                edge.append((a[j],i,j))
                ans += a[j]
    
    for k in range(n - 1):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] ,dist[i][k] + dist[k][j])
    
    edge.sort(reverse = True,key = lambda x:x[0])
    for c,a,b in edge:
        if dist[a][b] < c:
            ans = -1
            break
        for i in range(n):
            if i != a and i != b:
                if c == dist[a][i] + dist[i][b]:
                    ans -= c
                    break
    print(ans)   

if __name__=='__main__':
    main()

Fixed submission:
import sys 
MOD = 10 ** 9 + 7
INF = 10**5
from collections import deque

def main():
    n = int(input())
    dist = []
    edge = []
    ans = 0
    for i in range(n):
        a = list(map(int,input().split()))
        dist.append(a)
        for j in range(n):
            if i < j:
                edge.append((a[j],i,j))
                ans += a[j]
    
    for k in range(n - 1):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] ,dist[i][k] + dist[k][j])
    
    edge.sort(reverse = True,key = lambda x:x[0])
    for c,a,b in edge:
        if dist[a][b] < c:
            ans = -1
            break
        for i in range(n):
            if i != a and i != b:
                if c == dist[a][i] + dist[i][b]:
                    ans -= c
                    break
    print(ans)   

if __name__=='__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
from itertools import permutations

def main():
    n,m,r = map(int,input().split())
    dest = [int(i) - 1 for i in input().split()]
    dist = [[INF] * n for _ in range(n)]

    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j])
    
    ans = INF
    for ptr in permutations(range(r)):
        tmp = 0
        for i in range(r - 1):
            tmp += dist[dest[ptr[i]]][dest[ptr[i + 1]]]
        ans = min (ans, tmp)
    
    print(ans)

if __name__=='__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
from itertools import permutations

def main():
    n,m,r = map(int,input().split())
    dest = [int(i) - 1 for i in input().split()]
    dist = [[INF] * n for _ in range(n)]

    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j])
    
    ans = INF
    for ptr in permutations(range(r)):
        tmp = 0
        for i in range(r - 1):
            tmp += dist[dest[ptr[i]]][dest[ptr[i + 1]]]
        ans = min (ans, tmp)
    
    print(ans)

if __name__=='__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    edges=[[] for _ in range(n)]
    for i in range(n-1):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        edges[a].append([b,c])
        edges[b].append([a,c])
    q,k=map(int,input().split())
    k-=1
    
    dist=[10**9+1]*n
    dist[k]=0
    
    def dfs(s,before=-1):
       for edge in edges[s]:
           to=edge[0]
           c=edge[1]
           if to!=before:
               dist[to]=dist[s]+c
               dfs(to,s) 
              
    dfs(k)
    for i in range(q):
        x,y=map(int,input().split())
        x-=1
        y-=1
        print(dist[x]+dist[y])
if __name__=='__main__':
    main()

Fixed submission:
import heapq
def dijkstra(V, edges, s):
    inf=float('inf')

    dist=[inf]*V
    dist[s]=0
    
    que=[[0,s]]
    heapq.heapify(que) #最小値を管理 [dist[i],i]となる要素

    while  que:
        p=heapq.heappop(que) #距離が最小のものを取り出す
        dis=p[0]
        v=p[1]
        if dist[v] <dis:
            continue
        for edge in edges[v]:
            to_v=edge[0]
            cost=edge[1]
        
            if dist[to_v] > dist[v] + cost:
                dist[to_v]=dist[v]+cost
                heapq.heappush(que,[dist[to_v], to_v])
    
    return dist

def main():
    n=int(input())
    edges=[[] for _ in range(n)]
    for i in range(n-1):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        edges[a].append([b,c])
        edges[b].append([a,c])
    q,k=map(int,input().split())
    k-=1
   
    dist=dijkstra(n,edges,k)
    for i in range(q):
        x,y=map(int,input().split())
        x-=1
        y-=1
        print(dist[x]+dist[y])
if __name__=='__main__':
    main()
Buggy python submission (verdict: Runtime Error):
INF = 10 ** 20
MOD = 10 ** 9 + 7
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  heapq import heappop,heapify,heappush
from bisect import bisect_left
from functools import reduce
from math import gcd

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))

    if k > max(a):
        print('IMPOSSIBLE')
        return

    G = reduce(gcd,a)
    if k%G == 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBEL')
if __name__ == '__main__':
    main()


Fixed submission:
INF = 10 ** 20
MOD = 10 ** 9 + 7
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  heapq import heappop,heapify,heappush
from bisect import bisect_left
from functools import reduce
from fractions import gcd

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))

    if k > max(a):
        print('IMPOSSIBLE')
        return

    G = reduce(gcd,a)
    if k%G == 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
from itertools import permutations

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    
    depth = [-1] * n
    depth[0] = 0
    snuke = [0] * n
    snuke[-1] = 1
    children = [1] * n

    def dfs(i):
        if len(G[i]) == 0:
            return
        else:
            for e in G[i]:
                if depth[e] == -1:
                    depth[e] = depth[i] + 1
                    dfs(e)
                    snuke[i] |= snuke[e]
                    children[i] += children[e] 

    dfs(0)
    white = depth[-1]//2 + 1
    for i in range(n):
        if depth[i] == white and snuke[i]:
            sp = children[i]
            fp = n - sp
            break
    
    if  fp > sp:
        print('Fennec')
    else:
        print('Snuke')  
if __name__=='__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    
    depth = [-1] * n
    depth[0] = 0
    snuke = [0] * n
    snuke[-1] = 1
    children = [1] * n

    def dfs(i):
        if len(G[i]) == 0:
            return
        else:
            for e in G[i]:
                if depth[e] == -1:
                    depth[e] = depth[i] + 1
                    dfs(e)
                    snuke[i] |= snuke[e]
                    children[i] += children[e] 
  
    dfs(0)
    white = depth[-1]//2 + 1
    for i in range(n):
        if depth[i] == white and snuke[i]:
            sp = children[i]
            fp = n - sp
            break
    
    if  fp > sp:
        print('Fennec')
    else:
        print('Snuke')  
if __name__=='__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7
INF = 10  ** 7
def main():
    n,a,b = map(int,input().split())
    m = n//2
    Chemical = [tuple(map(int,input().split())) for _ in range(n)]
    Chemical1 = Chemical[:m]
    Chemical2 = Chemical[m:]
    Sum1 = [[INF] * 405 for _ in range(405)]
    Sum2 = [[INF] * 405 for _ in range(405)]
    for bit in range(1<<m):
        cost,v1,v2 = 0,0,0
        for i in range(m):
            if (bit>>i)&1:
                d,e,f = Chemical1[i]
                v1 += d
                v2 += e
                cost += f
        Sum1[v1][v2] = min(Sum1[v1][v2],cost)
    
    for bit in range(1<<(n - m)):
        cost,v1,v2 = 0,0,0
        for i in range(n - m):
            if (bit>>i)&1:
                d,e,f = Chemical2[i]
                v1 += d
                v2 += e
                cost += f
        Sum2[v1][v2] = min(Sum2[v1][v2],cost)
    
    ans = INF
    for i in range(405):
        for j in range(405):
            if Sum1[i][j] != INF:
                C = Sum1[i][j]
                k = max((i + a - 1)//a,(j + b - 1)//b,1)
                while k * a - i < 405 and k*b - j < 405:
                    if Sum2[k*a - i][k*b - j] != INF:
                        ans = min(ans,Sum2[k*a - i][k*b - j] + C)
                    k += 1
    print(ans if ans != INF else -1)
if __name__ == '__main__':
    main()

Fixed submission:
MOD = 10 ** 9 + 7
INF = 10  ** 7
def main():
    n,a,b = map(int,input().split())
    m = n//2
    Chemical = [tuple(map(int,input().split())) for _ in range(n)]
    Chemical1 = Chemical[:m]
    Chemical2 = Chemical[m:]
    Sum1 = [[INF] * 405 for _ in range(405)]
    Sum2 = [[INF] * 405 for _ in range(405)]
    for bit in range(1<<m):
        cost,v1,v2 = 0,0,0
        for i in range(m):
            if (bit>>i)&1:
                d,e,f = Chemical1[i]
                v1 += d
                v2 += e
                cost += f
        Sum1[v1][v2] = min(Sum1[v1][v2],cost)
    
    for bit in range(1<<(n - m)):
        cost,v1,v2 = 0,0,0
        for i in range(n - m):
            if (bit>>i)&1:
                d,e,f = Chemical2[i]
                v1 += d
                v2 += e
                cost += f
        Sum2[v1][v2] = min(Sum2[v1][v2],cost)
    
    ans = INF
    for i in range(405):
        for j in range(405):
            if Sum1[i][j] != INF:
                C = Sum1[i][j]
                k = max((i + a - 1)//a,(j + b - 1)//b,1)
                while k * a - i < 405 and k*b - j < 405:
                    if Sum2[k*a - i][k*b - j] != INF:
                        ans = min(ans,Sum2[k*a - i][k*b - j] + C)
                    k += 1
    print(ans if ans != INF else -1)
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
INF = 10**10
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from functools import lru_cache
from itertools import permutations

def main():
    n,m = map(int,input().split())
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0

    edge = []
    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c
        edge.append((a,b,c))
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
    
    cnt = 0
    for e in edge:
        a,b,c = e
        flag = True
        for i in range(n):
            for j in range(n):
                if dist[i][a] + c + dist[b][j] == dist[i][j]:
                    flag = False
                    break
            if flag == False:
                break
        
        if flag:
            cnt += 1
    
    print(cnt)

if __name__=='__main__':
    main() 

Fixed submission:
import sys
INF = 10**10
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from functools import lru_cache
from itertools import permutations

def main():
    n,m = map(int,input().split())
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0

    edge = []
    for _ in range(m):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        dist[a][b] = c
        dist[b][a] = c
        edge.append((a,b,c))
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
    
    cnt = 0
    for e in edge:
        a,b,c = e
        flag = True
        for i in range(n):
            for j in range(n):
                if dist[i][a] + c + dist[b][j] == dist[i][j]:
                    flag = False
                    break
            if flag == False:
                break
        
        if flag:
            cnt += 1
    
    print(cnt)

if __name__=='__main__':
    main()