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):
def main():
	N, M = map(int, input().split())
	points = [[] for _ in range(N+1)]
	for i in range(1, M+1):
		a, b, c = map(int, input().split())
		points[a].append([b, c, i])
		points[b].append([a, c, i])
	use = set()
	def dijksta(start):
		is_visited = [False]*(N+1)
		is_visited[0] = True
		is_visited[start] = True
		stack = list(points[start])
		edge = 0
		while stack:
			edge += 1
			stack.sort(key=lambda x: x[1])
			use_edge = stack.pop()
			cur = use_edge[0]
			dist = use_edge[1]
			use.add(use_edge[2])
			is_visited[cur] = True
			if all(is_visited):
				return edge
			add_stack = list(points[cur])
			removes = []
			for i, pair in enumerate(add_stack):
				if is_visited[pair[0]]:
					removes.append(i)
					continue
				add_stack[i][1] += dist
			removes.reverse()
			for i in removes:
				add_stack.pop(i)
			stack.extend(add_stack)
	for i in range(1, M+1):
		dijksta(i)
	ans = M - len(use)
	print(ans)

if __name__ == '__main__':
    main()

def main():
	N, M = map(int, input().split())
	points = [[] for _ in range(N+1)]
	for i in range(1, M+1):
		a, b, c = map(int, input().split())
		points[a].append([b, c, i])
		points[b].append([a, c, i])
	use = set()
	def dijksta(start):
		is_visited = [False]*(N+1)
		is_visited[0] = True
		is_visited[start] = True
		stack = list(points[start])
		while stack:
			stack.sort(key=lambda x: x[1])
			use_edge = stack.pop()
			cur = use_edge[0]
			dist = use_edge[1]
			use.add(use_edge[2])
			is_visited[cur] = True
			if all(is_visited):
				break
			add_stack = list(points[cur])
			removes = []
			for i, pair in enumerate(add_stack):
				if is_visited[pair[0]]:
					removes.append(i)
					continue
				add_stack[i][1] += dist
			removes.reverse()
			for i in removes:
				add_stack.pop(i)
			stack.extend(add_stack)
	for i in range(1, M+1):
		dijksta(i)
	ans = M - len(use)
	print(ans)

if __name__ == '__main__':
    main()

def main():
	INF = 10**9+7
	N, M = map(int, input().split())
	dist = [[INF for _ in range(N+1)] for _ in range(N+1)]
	for i in range(1, N+1):
		for j in range(1, N+1):
			if i == j:
				dist[i][j] = 0
	a, b, c = [0]*M, [0]*M, [0]*M
	for i in range(M):
		a[i], b[i], c[i] = map(int, input().split())
		dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i])
		dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i])
	for k in range(1, N+1):
		for i in range(1, N+1):
			for j in range(1, N+1):
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
	ans = M
	for i in range(M):
		shrotest = False
		for j in range(1, N+1):
			if dist[j][a[i]]+c[i] == dist[j][b[i]]:
				shrotest = True
		if shrotest:
			ans -= 1
	print(ans)

if __name__ == '__main__':
    main()

Verdicts: Runtime Error

Runtime Error

Accepted