Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())

lst = [1] * (n + 1)
if n == 1:
  print(0)
else:
  count = 0
  num = n
  for i in range(2, n + 1):
    if lst[i] == 0:
      continue
    for j in range(i, n + 1, i):
      lst[j] = 0
      if num % j == 0:
        num /= j
        count += 1
      if num % j == num:
        break
    if num == 1:
      break
  print(count)

Fixed submission:
n = int(input())

lst = []
while n % 2 == 0:
  lst.append(2)
  n //= 2
f = 3
while f * f <= n:
  if n % f == 0:
    lst.append(f)
    n //= f
  else:
    f += 2
if n != 1:
  lst.append(n)
#print(lst)
count = 0
while lst:
  s = 0
  i = 1
  num = lst[0]
  for ele in lst:
    if ele == num:
      s += 1
  for j in range(s):
    lst.remove(num)
  while s > 0:
    s -= i
    i += 1
    if s >= 0:
      count += 1
  #print(lst)
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
from math import floor

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

max_v = 0
if n < b:
  max_v = floor(a * n / b)
else:
  for i in range(b - 1, n + 1, b):
    t = floor(a * i / b) - a * floor(i / b)
    if t > max_v:
      max_v = t
print(max_v)

Fixed submission:
from math import floor

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

max_v = 0
if n < b:
  max_v = floor(a * n / b)
else:
  if b != 1:
    for i in range(b - 1, n + 1, b):
      j = 0
      t = floor(a * i / b) - a * j
      if t > max_v:
        max_v = t
      j += 1
print(max_v)

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

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

max_v = 0
for i in range(n + 1):
  t = floor(a * i / b) - a * floor(i / b)
  if t > max_v:
    max_v = t
print(max_v)

Fixed submission:
from math import floor

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

max_v = 0
if n < b:
  max_v = floor(a * n / b)
else:
  if b != 1:
    for i in range(b - 1, n + 1, b):
      j = 0
      t = floor(a * i / b) - a * j
      if t > max_v:
        max_v = t
      j += 1
print(max_v)
Buggy python submission (verdict: Runtime Error):
w = input()
l = len(w)
flag = True
for i in range((l - 1)/2):
  if w[i] != w[l - i - 1]:
    flag = False
    break
mid = (l - 1)/2
mid_mid = mid // 2
for i in range(mid_mid + 1):
  if w[i] != w[mid - i - 1] or not flag:
    flag = False
    break
  if w[i + mid + 1] != w[l - i - 1]:
    flag = False
    break
if flag:
  print('Yes')
else:
  print('No')

Fixed submission:
w = input()
l = len(w)
flag = True
for i in range((l - 1)//2):
  if w[i] != w[l - i - 1]:
    flag = False
    break
mid = (l - 1) // 2
mid_mid = mid // 2
for i in range(mid_mid + 1):
  if w[i] != w[mid - i - 1] or not flag:
    flag = False
    break
  if w[i + mid + 1] != w[l - i - 1]:
    flag = False
    break
if flag:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
lst = [int(i) for i in input().split()]
dic = {}
for i in range(n):
  if lst[i] not in dic:
    dic[lst[i]] = 1
  else:
    dic[lst[i]] += 1
#print(dic)
dic2 = {}
for key, value in dic.items():
  dic2[key] = [value * (value - 1) // 2, (value - 1) * (value - 2) // 2]
ans = {}
for i in range(n):
  count = 0
  m = lst[i]
  if m not in ans:
    for key, value in dic2.items():
      if key == m:
        count += value[1]
      else:
        count += value[0]
    ans[m] = count
  else:
    count = ans[m]
  print(count)

Fixed submission:
n = int(input())
lst = [int(i) for i in input().split()]
dic = {}
for i in range(n):
  if lst[i] not in dic:
    dic[lst[i]] = [1, 0, 0]
  else:
    dic[lst[i]][0] += 1
    dic[lst[i]][1] = dic[lst[i]][0] * (dic[lst[i]][0] - 1) // 2
    dic[lst[i]][2] = (dic[lst[i]][0] - 1) * (dic[lst[i]][0] - 2) // 2
#print(dic)
count = 0
for value in dic.values():
  count += value[1]
for i in range(n):
  m = lst[i]
  count -= dic[m][1]
  count += dic[m][2]
  print(count)
  count += dic[m][1]
  count -= dic[m][2]
Buggy python submission (verdict: Runtime Error):
n = int(input())
words = input()

count ≒ 0
for i in range(n - 2):
  if words[i] == 'A':
    if words[i + 1] == 'B':
      if words[i + 2] == 'C':
        count += 1
print(count)

Fixed submission:
n = int(input())
words = input()

count = 0
for i in range(n - 2):
  if words[i] == 'A':
    if words[i + 1] == 'B':
      if words[i + 2] == 'C':
        count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
k = int(input())
s = raw_input()

if k >= len(s):
    print(s)
else:
    print(s[0:k]+"...")


Fixed submission:
k = int(input())
s = input()

if k >= len(s):
    print(s)
else:
    print(s[0:k]+"...")
Buggy python submission (verdict: Runtime Error):
# coding: utf-8

n = input()

if n % 2 == 1:
    print(n/2 + 1)
else:
    print(n/2)

Fixed submission:
# coding: utf-8

n = input()

if n % 2 == 1:
    print(n/2 + 1)
else:
    print(n/2)

Buggy python submission (verdict: Runtime Error):
n = input()

if n % 2 == 1:
    print(n/2 + 1)
else:
    print(n/2)

Fixed submission:
# coding: utf-8

n = input()

if n % 2 == 1:
    print(n/2 + 1)
else:
    print(n/2)

Buggy python submission (verdict: Runtime Error):
# coding: utf-8

n = input()

if n % 2 == 1:
    print(n/2 + 1)
else:
    print(n/2)

Fixed submission:
# coding: utf-8

n = input()

if n % 2 == 1:
    print(n/2 + 1)
else:
    print(n/2)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy
from typing import List

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))


def solve(N: int, K: int, P: List[int], C: List[int]):
    ans = max(C)
    visited = [False] * N
    for i in range(N):
        if visited[i]:
            continue

        cycle = []
        to = i
        while not visited[to]:
            visited[to] = True
            cycle.append(C[to])
            to = P[to] - 1

        ans = max(ans, partial_solve(len(cycle), K, cycle))

    return ans


def partial_solve(N: int, K: int, A: List[int]):
    ret = max(A)
    B = [0] * (3 * N + 1)
    for i in range(1, 3 * N + 1):
        B[i] = B[i - 1] + A[(i - 1) % N]

    if N > K:
        for l in range(1, N + 1):
            for r in range(l, l + K):
                ret = max(ret, B[r] - B[l - 1])

    else:
        if B[N] < 0:
            K = N
            for l in range(1, N + 1):
                for r in range(l, l + K):
                    ret = max(ret, B[r] - B[l - 1])
        else:
            cnt = K // N - 1

            K = K % N + N

            for l in range(1, N + 1):
                for r in range(l, l + K):
                    ret = max(ret, B[r] - B[l - 1])

            ret += cnt * B[N]

    return ret

print(solve(N, K, P, C))


Fixed submission:
from typing import List

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))


def solve(N: int, K: int, P: List[int], C: List[int]):
    ans = max(C)
    visited = [False] * N
    for i in range(N):
        if visited[i]:
            continue

        cycle = []
        to = i
        while not visited[to]:
            visited[to] = True
            cycle.append(C[to])
            to = P[to] - 1

        ans = max(ans, partial_solve(len(cycle), K, cycle))

    return ans


def partial_solve(N: int, K: int, A: List[int]):
    ret = max(A)
    B = [0] * (3 * N + 1)
    for i in range(1, 3 * N + 1):
        B[i] = B[i - 1] + A[(i - 1) % N]

    if N > K:
        for l in range(1, N + 1):
            for r in range(l, l + K):
                ret = max(ret, B[r] - B[l - 1])

    else:
        if B[N] < 0:
            K = N
            for l in range(1, N + 1):
                for r in range(l, l + K):
                    ret = max(ret, B[r] - B[l - 1])
        else:
            cnt = K // N - 1

            K = K % N + N

            for l in range(1, N + 1):
                for r in range(l, l + K):
                    ret = max(ret, B[r] - B[l - 1])

            ret += cnt * B[N]

    return ret

print(solve(N, K, P, C))
Buggy python submission (verdict: Runtime Error):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, K = map(int, input().split())

A = list(map(int, input().split()))


def ok(X):
    cnt = 0
    for a in A:
        cnt += (a - 1) // X

    return cnt <= K


def solve():
    l, r = -1, 1000000000

    while l + 1 < r:
        c = (l + r) // 2
        if ok(c):
            r = c
        else:
            l = c

    return r

print(solve())

Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, K = map(int, input().split())

A = list(map(int, input().split()))


def ok(X):
    cnt = 0
    for a in A:
        cnt += (a - 1) // X

    return cnt <= K


def solve():
    l, r = 0, 1000000000

    while l + 1 < r:
        c = (l + r) // 2
        if ok(c):
            r = c
        else:
            l = c

    return r


print(solve())
Buggy python submission (verdict: Runtime Error):
N = int(input())

cnt = [0] * 6 * 10000 + 1

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            cnt[x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x] += 1

for i in range(1, N + 1):
    print(cnt[i])


Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

cnt = [0] * 10010

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            calc = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if calc <= N:
                cnt[calc] += 1

for i in range(1, N + 1):
    print(cnt[i])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

s = 0
for i in range(N):
    s += i

print(s)

Fixed submission:
N = int(input())

s = N * (N - 1) // 2

print(s)
Buggy python submission (verdict: Runtime Error):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, X = map(int, input().split())
A = list(map(int, input().split()))

D = 0
cnt = 0
while D <= X:
    D += A[cnt]
    cnt += 1

print(cnt)

Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, X = map(int, input().split())
A = list(map(int, input().split()))

D = 0
cnt = 0
while D <= X and cnt <= N:
    if cnt != N:
        D += A[cnt]
    cnt += 1

print(cnt)
Buggy python submission (verdict: Runtime Error):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
A = list(map(int, input().split()))

B = [0] * M
s = 0
ans = 0
B[0] = 1
for a in A:
    s = (s + a) % M
    ans += B[s]
    B[s] += 1

print(ans)


Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
A = list(map(int, input().split()))

B = {}
s = 0
ans = 0
B[0] = 1
for a in A:
    s = (s + a) % M
    ans += B.get(s, 0)
    B[s] = B.get(s, 0) + 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
X, Y, Z = [0] * N, [0] * N, [0] * N

for i in range(N):
    X[i], Y[i], Z[i] = map(int, input().split())

codes = [[1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1], [-1, 1, 1], [-1, 1, -1], [-1, -1, 1], [-1, -1, -1]]


def calc(code, idx):
    return code[0] * X[idx] + code[1] * Y[idx] + code[2] * Z[idx]


ans = 0
INF = 1 << 60
for code in codes:
    dp = [-INF] * (M + 1)
    dp[0] = 0
    for i in range(N):
        tmp = [-INF] * (M + 1)
        tmp[0] = 0
        for j in range(M, 0, -1):
            if dp[j - 1] >= 0:
                tmp[j] = max(dp[j], dp[j - 1] + calc(code, i))

        dp = tmp
    #     print("", dp)
    # print(dp)
    ans = max(ans, dp[M])

print(ans)

Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
X, Y, Z = [0] * N, [0] * N, [0] * N

for i in range(N):
    X[i], Y[i], Z[i] = map(int, input().split())

codes = [[1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1], [-1, 1, 1], [-1, 1, -1], [-1, -1, 1], [-1, -1, -1]]


def calc(code, idx):
    return code[0] * X[idx] + code[1] * Y[idx] + code[2] * Z[idx]


INF = 1 << 60
ans = -INF
for code in codes:
    ar = [0] * N

    for i in range(N):
        ar[i] = calc(code, i)

    ar.sort(reverse=True)

    ans = max(ans, sum(ar[:M]))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(20):
        if i + six <= N:
            dp[i + six] = min(dp[i + six], dp[i] + 1)
        if i + nine <= N:
            dp[i + nine] = min(dp[i + nine], dp[i] + 1)
        six *= six
        nine *= nine

print(dp[N])

Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(10):
        if i + six <= N:
            dp[i + six] = min(dp[i + six], dp[i] + 1)
        if i + nine <= N:
            dp[i + nine] = min(dp[i + nine], dp[i] + 1)
        six *= 6
        nine *= 9

print(dp[N])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(20):
        if i + six ** p <= N:
            dp[i + six ** p] = min(dp[i + six ** p], dp[i] + 1)
        if i + nine ** p <= N:
            dp[i + nine ** p] = min(dp[i + nine ** p], dp[i] + 1)

print(dp[N])

Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
    dp[i + 1] = min(dp[i + 1], dp[i] + 1)
    six = 6
    nine = 9
    for p in range(10):
        if i + six <= N:
            dp[i + six] = min(dp[i + six], dp[i] + 1)
        if i + nine <= N:
            dp[i + nine] = min(dp[i + nine], dp[i] + 1)
        six *= 6
        nine *= 9

print(dp[N])
Buggy python submission (verdict: Runtime Error):
from typing import List

N, M = map(int, input().split())

g = [[] for _ in range(N)]

for i in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    g[l].append((r, d))
    g[r].append((l, d))


def ok(cur: int, ds: int, dists: List[int]):
    dists[cur] = ds

    flag = True
    for nx, d in g[cur]:
        if dists[nx] >= 0:
            flag &= abs(dists[nx] - dists[cur]) == d
        elif flag:
            flag &= ok(nx, ds + d, dists)


    return flag


dists = [-1] * N
ans = True
for i in range(N):
    if ans and dists[i] < 0:
        ans &= ok(i, 0, dists)

print("Yes" if ans else "No")


Fixed submission:
import sys
from typing import List, Optional

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())

g = [[] for _ in range(N)]

for i in range(M):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    g[l].append((r, d))
    g[r].append((l, -d))


def ok(cur: int, ds: int, dists: List[Optional[int]]) -> bool:
    dists[cur] = ds

    flag = True
    for nx, d in g[cur]:
        if dists[nx] != None:
            flag &= dists[nx] - dists[cur] == d
        elif flag:
            flag &= ok(nx, ds + d, dists)

    return flag


dists = [None] * N
ans = True
for i in range(N):
    if ans and dists[i] == None:
        ans &= ok(i, 0, dists)

print("Yes" if ans else "No")
Buggy python submission (verdict: Runtime Error):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, Z, W = map(int, input().split())

A = list(map(int, input().split()))

print(abs(A[-1] - W), abs(A[-1] - A[-2]))


Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, Z, W = map(int, input().split())

A = list(map(int, input().split()))

if N == 1:
    print(abs(A[-1] - W))
else:
    print(max(abs(A[-1] - W), abs(A[-1] - A[-2])))
Buggy python submission (verdict: Runtime Error):
a,b = input().split()

print("H" if (a == "H" ^ b == "H") else "D")


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

print("H" if (a == "D") ^ (b == "H") else "D")

Buggy python submission (verdict: Runtime Error):
a,b = input().split()

print("H" if a == "H" ^ b == "H" else "D")

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

print("H" if (a == "D") ^ (b == "H") else "D")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, Ma, Mb = map(int, input().split())
A = [0] * N
B = [0] * N
C = [0] * N

for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

INF = 1 << 50
LEN = 500
dp = [[INF] * (LEN + 1) for _ in range(LEN + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(LEN, A[i] - 1, -1):
        for k in range(LEN, B[i] - 1, -1):
            dp[j][k] = min(dp[j][k], dp[j - A[i]][k - B[i]] + C[i])

cnt = 1
ans = INF
while cnt * Ma < LEN and cnt * Mb < LEN:
    ans = min(ans, dp[cnt * Ma][cnt * Mb])
    cnt += 1

print(ans if ans != INF else -1)

Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, Ma, Mb = map(int, input().split())
A = [0] * N
B = [0] * N
C = [0] * N

for i in range(N):
    A[i], B[i], C[i] = map(int, input().split())

INF = 1 << 50
LEN = 500
dp = [[INF] * (LEN + 1) for _ in range(LEN + 1)]
dp[0][0] = 0

for i in range(N):
    for j in range(LEN, A[i] - 1, -1):
        for k in range(LEN, B[i] - 1, -1):
            dp[j][k] = min(dp[j][k], dp[j - A[i]][k - B[i]] + C[i])

cnt = 1
ans = INF
while cnt * Ma < LEN and cnt * Mb < LEN:
    ans = min(ans, dp[cnt * Ma][cnt * Mb])
    cnt += 1

print(ans if ans != INF else -1)
Buggy python submission (verdict: Runtime Error):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())
A = list(map(int, input().split()))

B = [0] * 10001
for a in A:
    B[a] += 1
cnt2 = 0
cnt1 = 0
ans = 0
for b in B:
    if b > 2:
        cnt2 += 1
    if b > 1:
        cnt1 += 1
    if b > 0:
        ans += 1
if cnt1 % 2 == 1 and cnt2 == 0:
    ans -= 1
print(ans)

Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())
A = list(map(int, input().split()))

B = [0] * 100001
for a in A:
    B[a] += 1
cnt1 = 0
ans = 0
for b in B:
    if b > 1 and b % 2 == 0:
        cnt1 += 1
    if b > 0:
        ans += 1
if cnt1 % 2 == 1:
    ans -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]

INF = 1 << 28
ds = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    ds[i][i] = 0

for abc in ABC:

    ds[abc[0]][abc[1]] = ds[abc[1]][abc[0]] = min(ds[abc[0]][abc[1]], abc[2])

for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            ds[i][j] = ds[j][i] = min(ds[i][j], ds[i][k] + ds[k][j])
cnt = 0
for abc in ABC:
    used = False
    for i in range(N + 1):
        for j in range(N + 1):
            if ds[i][j] == ds[i][abc[0]] + abc[2] + ds[abc[1]][j]:
                used = True
    if not used:
        cnt += 1

print(cnt)


Fixed submission:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]

INF = 1 << 28
ds = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    ds[i][i] = 0

for abc in ABC:

    ds[abc[0]][abc[1]] = ds[abc[1]][abc[0]] = min(ds[abc[0]][abc[1]], abc[2])

for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            ds[i][j] = ds[j][i] = min(ds[i][j], ds[i][k] + ds[k][j])
cnt = 0
for abc in ABC:
    used = False
    for i in range(N + 1):
        for j in range(N + 1):
            if ds[i][j] == ds[i][abc[0]] + abc[2] + ds[abc[1]][j]:
                used = True
    if not used:
        cnt += 1

print(cnt)