Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush
import sys
input=sys.stdin.readline 

class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()
        self.edges = []
 
    def add_edge(self, a, b, weight=1):
        self.graph[a].append((b, weight))
        self.vertices |= {a, b}
        self.edges.append((a, b, weight))
 
    def get_vertices(self):
        return sorted(list(self.vertices))
 
    def num_of_vertices(self):
        return len(self.vertices)
 
    def get_edges(self):
        return self.edges
 
    def num_of_edges(self):
        return len(self.edges)
 
class Dijkstra:
 
    def __init__(self, graph, start):
        self.g = graph.graph
 
        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0
 
        self.prev = defaultdict(lambda: None)
 
        self.Q = []
        heappush(self.Q, (0, start))
 
        while self.Q:
            dist_u, u = heappop(self.Q)
 
            if self.dist[u] < dist_u:
                continue
 
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
 
 
    def shortest_distance(self, goal):
 
        return self.dist[goal]
 
    def shortest_path(self, goal):
 
        path = []
        vertice = goal
        cnt = 0
        while vertice is not None:
            path.append(vertice)
            cnt += 1
            vertice = self.prev[vertice]
 
        return path, cnt

N, M = map(int, input().split())
G = Graph()
T = []
C = defaultdict(int)
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, c)
    G.add_edge(b, a, c)
    T.append(tuple(sorted([a, b])))

for i in range(1, N+1):
    for j in range(1, N+1):
        D = Dijkstra(G, i)
        P, L = D.shortest_path(j)
        for k in range(L-1):
            a, b = P[k], P[k+1]
            C[tuple(sorted([a, b]))] = 1

ans = 0
for a, b in T:
    if C[(a, b)] == 0:
        ans += 1

print(ans)


Fixed submission:
N, M = map(int, input().split())
inf = float("inf")
dist = [[inf for _ in range(N)] for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

T = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    T.append((a, b, c))
    dist[a][b] = min(dist[a][b], c)
    dist[b][a] = min(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 = M
for a, b, c in T:
    check = False
    for i in range(N):
        if dist[i][a] + c == dist[i][b]:
            check = True
    if check:
        ans -= 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush
import sys
input=sys.stdin.readline 

class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()
        self.edges = []
 
    def add_edge(self, a, b, weight=1):
        self.graph[a].append((b, weight))
        self.vertices |= {a, b}
        self.edges.append((a, b, weight))
 
    def get_vertices(self):
        return sorted(list(self.vertices))
 
    def num_of_vertices(self):
        return len(self.vertices)
 
    def get_edges(self):
        return self.edges
 
    def num_of_edges(self):
        return len(self.edges)
 
class Dijkstra:
 
    def __init__(self, graph, start):
        self.g = graph.graph
 
        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0
 
        self.prev = defaultdict(lambda: None)
 
        self.Q = []
        heappush(self.Q, (0, start))
 
        while self.Q:
            dist_u, u = heappop(self.Q)
 
            if self.dist[u] < dist_u:
                continue
 
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
 
 
    def shortest_distance(self, goal):
 
        return self.dist[goal]
 
    def shortest_path(self, goal):
 
        path = []
        vertice = goal
        while vertice is not None:
            path.append(vertice)
            vertice = self.prev[vertice]
 
        return path[::-1]

N, M = map(int, input().split())
G = Graph()
T = []
C = defaultdict(int)
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, c)
    G.add_edge(b, a, c)
    T.append(tuple(sorted([a, b])))

for i in range(1, N+1):
    for j in range(1, N+1):
        D = Dijkstra(G, i)
        P = D.shortest_path(j)
        for k in range(len(P)-1):
            a, b = P[k], P[k+1]
            C[tuple(sorted([a, b]))] = 1

ans = 0
for a, b in T:
    if C[(a, b)] == 0:
        ans += 1

print(ans)

Fixed submission:
N, M = map(int, input().split())
inf = float("inf")
dist = [[inf for _ in range(N)] for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

T = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    T.append((a, b, c))
    dist[a][b] = min(dist[a][b], c)
    dist[b][a] = min(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 = M
for a, b, c in T:
    check = False
    for i in range(N):
        if dist[i][a] + c == dist[i][b]:
            check = True
    if check:
        ans -= 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import heappop, heappush
 
class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()
        self.edges = []
 
    def add_edge(self, a, b, weight=1):
        self.graph[a].append((b, weight))
        self.vertices |= {a, b}
        self.edges.append((a, b, weight))
 
    def get_vertices(self):
        return sorted(list(self.vertices))
 
    def num_of_vertices(self):
        return len(self.vertices)
 
    def get_edges(self):
        return self.edges
 
    def num_of_edges(self):
        return len(self.edges)
 
class Dijkstra:
 
    def __init__(self, graph, start):
        self.g = graph.graph
 
        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0
 
        self.prev = defaultdict(lambda: None)
 
        self.Q = []
        heappush(self.Q, (0, start))
 
        while self.Q:
            dist_u, u = heappop(self.Q)
 
            if self.dist[u] < dist_u:
                continue
 
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
 
 
    def shortest_distance(self, goal):
 
        return self.dist[goal]
 
    def shortest_path(self, goal):
 
        path = []
        vertice = goal
        while vertice is not None:
            path.append(vertice)
            vertice = self.prev[vertice]
 
        return path[::-1]

N, M = map(int, input().split())
G = Graph()
T = []
C = defaultdict(int)
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, c)
    G.add_edge(b, a, c)
    T.append(tuple(sorted([a, b])))

for i in range(1, N+1):
    for j in range(1, N+1):
        D = Dijkstra(G, i)
        P = D.shortest_path(j)
        for k in range(len(P)-1):
            a, b = P[k], P[k+1]
            C[tuple(sorted([a, b]))] = 1

ans = 0
for a, b in T:
    if C[(a, b)] == 0:
        ans += 1

print(ans)

Fixed submission:
N, M = map(int, input().split())
inf = float("inf")
dist = [[inf for _ in range(N)] for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

T = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    T.append((a, b, c))
    dist[a][b] = min(dist[a][b], c)
    dist[b][a] = min(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 = M
for a, b, c in T:
    check = False
    for i in range(N):
        if dist[i][a] + c == dist[i][b]:
            check = True
    if check:
        ans -= 1
print(ans)