Problem: You are given an undirected connected weighted graph with N vertices and M edges that contains neither self-loops nor double edges.   The i-th (1≤i≤M) edge connects vertex a_i and vertex b_i with a distance of c_i.   Here, a _self-loop_ is an edge where a_i = b_i (1≤i≤M), and _double edges_ are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).   A _connected graph_ is a graph where there is a path between every pair of different vertices.   Find the number of the edges that are not contained in any shortest path between any pair of different vertices.

Submission attempts (in order):
g = Graph()
N,M = list(map(int, input().split()))
INF = 10**9+7
A = [[INF if i!=j else 0 for i in range(N)] for j in range(N)]
S=[]
E=[]
W=[]

for i in range(M):
    s,e,w=list(map(int,input().split()))
    g.add_edge(s-1, e-1, w)
    g.add_edge(e-1, s-1, w)
    S.append(s-1)
    E.append(e-1)
    W.append(w)

for i in range(N):
    d = Dijkstra(g, i)
    for j in range(i+1,N):
        dist = d.shortest_distance(j)
        A[i][j] = dist
        A[j][i] = dist
        
ans=M
for i in range(M):
    shortest = False
    for j in range(N):
        if A[j][S[i]] + W[i] == A[j][E[i]]:
            shortest = True
    if shortest:
        ans-=1

print(ans)

from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):
    

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    

    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, (self.dist[start], 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 = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

g = Graph()
N,M = list(map(int, input().split()))
INF = 10**9+7
A = [[INF if i!=j else 0 for i in range(N)] for j in range(N)]
S=[]
E=[]
W=[]

for i in range(M):
    s,e,w=list(map(int,input().split()))
    g.add_edge(s-1, e-1, w)
    g.add_edge(e-1, s-1, w)
    S.append(s-1)
    E.append(e-1)
    W.append(w)

for i in range(N):
    d = Dijkstra(g, i)
    for j in range(i+1,N):
        dist = d.shortest_distance(j)
        A[i][j] = dist
        A[j][i] = dist
        
ans=M
for i in range(M):
    shortest = False
    for j in range(N):
        if A[j][S[i]] + W[i] == A[j][E[i]]:
            shortest = True
    if shortest:
        ans-=1

print(ans)

Verdicts: Runtime Error

Accepted