Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import deque
    from itertools import combinations
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, c, idx))  # to,weight,idx
        g[b].add((a, c, idx))  # to,weight,idx

    used_edge = 0

    dq = deque()
    for frm, to in combinations(range(N), r=2):
        dq.append((frm, 0))

        dist = [1000 * 100 + 10] * N
        dist[frm] = 0
        while dq:
            v, c = dq.popleft()
            if dist[v] < c: continue
            for u, dc, idx in g[v]:
                nc = c + dc
                if dist[u] > nc:
                    dist[u] = nc
                    dq.append((u, nc))

        dq.append((to, 0))
        while dq:
            v, b = dq.popleft()
            if v == frm:
                used_edge |= b
                continue

            for u, dc, idx in g[v]:
                if dist[u] == dist[v] - dc:
                    dq.append((u, b | 1 << idx))

    print(M - bin(used_edge).count('1'))


if __name__ == '__main__':
    main()


Fixed submission:
inf = 1000 * 1000 + 10

n, m = map(int, input().split())

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

# print(g)

need = set()
for a, b, c in e:
    for s in range(n):
        for t in range(n):
            if g[s][t] == g[s][a] + c + g[b][t]:
                need.add((a, b))
                break
        else:
            continue
        break
# print(need)
print(m - len(need))

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import deque
    from itertools import combinations
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, c, idx))  # to,weight,idx
        g[b].add((a, c, idx))  # to,weight,idx

    used_edge = 0

    dq = deque()
    for frm, to in combinations(range(N), r=2):
        dq.append((frm, 0))

        dist = [1000 * 100 + 10] * N
        dist[frm] = 0
        while dq:
            v, c = dq.popleft()
            if dist[v] < c: continue
            for u, dc, idx in g[v]:
                if dist[u] > c + dc:
                    dist[u] = c + dc
                    dq.append((u, dist[u]))

        dq.append((to, 0))
        while dq:
            v, b = dq.popleft()
            if v == frm:
                used_edge |= b
                continue

            for u, dc, idx in g[v]:
                if dist[u] == dist[v] - dc:
                    dq.append((u, b | 1 << idx))

    print(M - bin(used_edge).count('1'))


if __name__ == '__main__':
    main()


Fixed submission:
inf = 1000 * 1000 + 10

n, m = map(int, input().split())

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

# print(g)

need = set()
for a, b, c in e:
    for s in range(n):
        for t in range(n):
            if g[s][t] == g[s][a] + c + g[b][t]:
                need.add((a, b))
                break
        else:
            continue
        break
# print(need)
print(m - len(need))

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from collections import deque
    from itertools import combinations

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

    g = tuple(set() for _ in range(N))
    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, c, idx))  # to,weight,idx
        g[b].add((a, c, idx))  # to,weight,idx

    not_used_edge = [True] * M

    for frm, to in combinations(range(N), r=2):
        dq = deque()
        dq.append((frm, 0))

        dist = [1000 * 100 + 10] * N
        dist[frm] = 0
        while dq:
            v, c = dq.popleft()
            if dist[v] < c: continue
            for u, dc, idx in g[v]:
                if dist[u] > c + dc:
                    dist[u] = c + dc
                    dq.append((u, dist[u]))

        dq = deque()
        dq.append((to, 0))
        while dq:
            v, b = dq.popleft()
            if v == frm:
                for j in range(M):
                    if (b >> j) & 1:
                        not_used_edge[j] = False
                continue

            for u, dc, idx in g[v]:
                if dist[u] == dist[v] - dc:
                    dq.append((u, b | 1 << idx))

    print(sum(not_used_edge))


if __name__ == '__main__':
    main()


Fixed submission:
inf = 1000 * 1000 + 10

n, m = map(int, input().split())

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

# print(g)

need = set()
for a, b, c in e:
    for s in range(n):
        for t in range(n):
            if g[s][t] == g[s][a] + c + g[b][t]:
                need.add((a, b))
                break
        else:
            continue
        break
# print(need)
print(m - len(need))

Buggy python submission (verdict: Runtime Error):
from heapq import heappop, heappush
from math import inf


def dijkstra_need_edge(s):
    used = [False] * n
    used[s] = True

    dist = [inf] * n
    dist[s] = 0

    hq = []
    for e in g[s]:
        heappush(hq, e)

    need_edge = set()
    while hq:
        w, t, ind = heappop(hq)
        if used[t]: continue
        need_edge.add(ind)
        used[t] = True
        dist[t] = w
        add_es = map(lambda x: (dist[t] + x[0], x[1], x[2]), g[t])
        for e in add_es:
            heappush(hq, e)
    return need_edge


n, m = map(int, input().split())

g = tuple(set() for _ in range(n))
for ind in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a].add((c, b, ind))
    g[b].add((c, a, ind))

st = set()
for v in range(n):
    st |= dijkstra_need_edge(v)
print(m - len(st))


Fixed submission:
inf = 1000 * 1000 + 10

n, m = map(int, input().split())

g = tuple([inf] * n for _ in range(n))
e = set()
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    e.add((a, b, c))

for i in range(n):
    g[i][i] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

# print(g)

need = set()
for a, b, c in e:
    for s in range(n):
        for t in range(n):
            if g[s][t] == g[s][a] + c + g[b][t]:
                need.add((a, b))
                break
        else:
            continue
        break
# print(need)
print(m - len(need))