Problem:
 Score : 400 points    Problem Statement 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.      Constraints  2≤N≤100   N-1≤M≤min(N(N-1)/2,1000)   1≤a_i,b_i≤N   1≤c_i≤1000  c_i is an integer.  The given graph contains neither self-loops nor double edges.  The given graph is connected.         Input The input is given from Standard Input in the following format:  N  M  a_1  b_1  c_1  a_2  b_2  c_2  :  a_M  b_M  c_M       Output Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.        Sample Input 1 3 3
1 2 1
1 3 1
2 3 3      Sample Output 1 1  In the given graph, the shortest paths between all pairs of different vertices are as follows:   The shortest path from vertex 1 to vertex 2 is: vertex 1 → vertex 2 , with the length of 1 .  The shortest path from vertex 1 to vertex 3 is: vertex 1 → vertex 3 , with the length of 1 .  The shortest path from vertex 2 to vertex 1 is: vertex 2 → vertex 1 , with the length of 1 .  The shortest path from vertex 2 to vertex 3 is: vertex 2 → vertex 1 → vertex 3 , with the length of 2 .  The shortest path from vertex 3 to vertex 1 is: vertex 3 → vertex 1 , with the length of 1 .  The shortest path from vertex 3 to vertex 2 is: vertex 3 → vertex 1 → vertex 2 , with the length of 2 .   Thus, the only edge that is not contained in any shortest path, is the edge of length 3 connecting vertex 2 and vertex 3 , hence the output should be 1 .       Sample Input 2 3 2
1 2 1
2 3 1      Sample Output 2 0  Every edge is contained in some shortest path between some pair of different vertices.

Solution (Python):
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: 
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    
    return [0 if x is None else x for x in A]

shrtest = [[0]*(N+1)]
for a in range(1, N+1):
    sub_shrtest = dijkstra(graph, a)
    shrtest.append(sub_shrtest)


ans = 0
for a,b,c in edges:
    if shrtest[a][b] != c:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
abc= [list(map(int,input().split())) for _ in [0]*M]
d = [[10000*N]*N for _ in [0]*N]
for a,b,c in abc:
    d[a-1][b-1]=c
    d[b-1][a-1]=c
for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])
ans=sum(d[a-1][b-1]<c for a,b,c in abc)
print(ans)

Solution (Python):
from copy import deepcopy
N, M = map(int, input().split())
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


Shortest = deepcopy(G)
for k in range(N):
    for i in range(N):
        for j in range(N):
            Shortest[i][j] = min(Shortest[i][j], Shortest[i][k] + Shortest[k][j])


ans = 0
for i in range(N):
    for j in range(N):
        if G[i][j] == float('inf'):
            continue
        if G[i][j] != Shortest[i][j]:
            ans += 1

print(ans // 2)

Solution (Python):


from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra



N, M = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

for _ in range(M):
    
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1, pre = dijkstra(graph, directed=False, unweighted=False, return_predecessors =True)



path = [[0] * N for j in range(N)]
for i in range(N):
    for j in range(N):
        if pre[i][j] != -9999:
            if j < pre[i][j]:
                path[j][pre[i][j]] = 1
            else:
                path[pre[i][j]][j] = 1

print(M-sum(map(sum, path)))

Solution (Python):


from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra



N, M = [int(i) for i in input().split()]

rows = []
cols = []
weights = []

for _ in range(M):
    
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1, pre = dijkstra(graph, directed=False, unweighted=False, return_predecessors =True)



path = []
for i in range(N):
    for j in range(N):
        if pre[i][j] != -9999:
            if j < pre[i][j]:
                path.append([j,pre[i][j]])
            else:
                path.append([pre[i][j], j])
path = list(map(list, set(map(tuple, path))))
print(M-len(path))

Solution (Python):
import copy
N, M = map(int, input().split())
INF = 2 ** 63 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    d[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c

d_original = copy.deepcopy(d)

for k in range(1, N+1):
    for j in range(1, N+1):
        for i in range(1, N+1):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if d_original[i][j] != INF and d[i][j] != d_original[i][j]:
            ans += 1
print(ans)

Solution (Python):
import copy
N, M = map(int, input().split())
INF = 2 ** 63 - 1
d = [[INF for i in range(N+1)] for j in range(N+1)]
for i in range(N+1):
    d[i][i] = 0

for i in range(M):
    a, b, c = map(int, input().split())
    d[a][b] = c
    d[b][a] = c

d_original = copy.deepcopy(d)

for k in range(1, N+1):
    for j in range(1, N+1):
        for i in range(1, N+1):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if d_original[i][j] != INF and d[i][j] != d_original[i][j]:
            ans += 1
print(ans)

Solution (Python):
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()

Solution (Python):
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d


n, w = map(int, input().split())
INF = 10 ** 5
d = [[INF for i in range(n)] for i in range(n)]
e_list = []
for i in range(w):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
    e_list.append([x, y, z])
for i in range(n):
    d[i][i] = 0

warshall_floyd(d)
ans = w
for x, y, z in e_list:
    
    if d[x][y] == z:
        ans -= 1
print(ans)

Solution (Python):

import sys
import heapq
import copy
import itertools

inf = float('inf')

def path(u, v):
    return frozenset((u, v))


class Graph_dijkstra(object):
    def __init__(self, V: "List[int]", E: "Set[FrozenSet[int, int]]", L: "Dict[FrozenSet[int, int], int]"):
        self.V = V
        self.E = E
        self.L = L
        self.E_shortest = copy.deepcopy(E)
        self.adjacent = self.init_adjacent() 
        self.shortest_path = self.init_shortest_path() 
    
    def init_adjacent(self):
        ret = {v: [] for v in self.V}
        for e in self.E:
            el = list(e)
            ret[el[0]].append(el[1])
            ret[el[1]].append(el[0])
        return ret
    
    def init_shortest_path(self):
        ret = {path(s, g): inf for s, g in itertools.permutations(self.V, 2)}
        for v in self.V:
            ret[path(v, v)] = 0
        return ret
    
    def dijkstra(self, s: int, g: int):
        d = self.shortest_path[path(s, g)]
        if d < inf:
            return d

        D = {v: inf for v in self.V}
        D[s] = 0
        prev = {v: None for v in self.V}
        Q = [(0, s)]

        while len(Q) > 0:
            du, u = heapq.heappop(Q)
            for v in self.adjacent[u]:
                e = path(u, v)
                alt = du + self.L[e]
                if alt < D[v]:
                    D[v] = alt
                    prev[v] = u
                    heapq.heappush(Q, (D[v], v))

        for v in self.V:
            self.shortest_path[path(s, v)] = D[v]

        return self.shortest_path[path(s, g)]


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    V = list(range(N))
    E = set()
    L = dict()
    
    for i in range(M):
        e = path(a[i], b[i])
        E.add(e)
        L[e] = c[i]

    G = Graph_dijkstra(V, E, L)
    count = 0
    for e in E:
        el = list(e)
        path_len = G.dijkstra(el[0], el[1])
        if path_len < L[e]:
            count += 1
    print(count)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    c = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))-1
        b[i] = int(next(tokens))-1
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0]*M
b = [0]*M
c = [0]*M
for i in range(M):
    input_data = input().split()
    a[i], b[i], c[i] = map(int, input_data)
    a[i] -=1
    b[i] -=1

MAX = 10**10
dist = [[MAX for j in range(N)] for i in range(N)]


for i in range(N):
    dist[i][i] = 0

for i in range(M):
    dist[a[i]][b[i]] = c[i]
    dist[b[i]][a[i]] = c[i]

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 = 0
for i in range(M):
    if dist[a[i]][b[i]] < c[i]:
        ans += 1

print(ans)

Solution (Python):
import itertools

n, m = map(int, input().split())
d = []
for _ in range(m):
    a, b, c = map(int, input().split())
    d.append((a - 1, b - 1, c))

wf = [[float('inf')] * n for _ in range(n)]
for a, b, c in d:
    wf[a][b] = wf[b][a] = c
for i in range(n):
    wf[i][i] = 0

for k, i, j in itertools.product(range(n), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

ans = 0
for a, b, c in d:
    used = False
    for i in range(n):
        for j in range(i + 1, n):
            if wf[i][a] + c + wf[b][j] == wf[i][j] \
                    or wf[i][b] + c + wf[a][j] == wf[i][j] \
                    or wf[j][a] + c + wf[b][i] == wf[j][i] \
                    or wf[j][b] + c + wf[a][i] == wf[j][i]:
                used = True
            
    if not used:
        ans += 1

print(ans)

Solution (Python):
class Dijkstra: 
    def __init__(self, route_map, start_point, goal_point=None):
        self.route_map = route_map 
        self.start_point = start_point 
        self.goal_point = goal_point

    def execute(self):
        import heapq
        num_of_city = len(self.route_map) 
        dist = [float("inf") for _ in range(num_of_city)] 
        prev = [float("inf") for _ in range(num_of_city)] 

        dist[self.start_point] = 0 
        heap_q = [] 
        heapq.heappush(heap_q, (0, self.start_point)) 
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q) 

            if dist[src] < prev_cost: 
                continue

            for dest, cost in self.route_map[src].items(): 
                if cost != float("inf") and dist[dest] > dist[src] + cost: 
                    dist[dest] = dist[src] + cost 
                    heapq.heappush(heap_q, (dist[dest], dest)) 
                    prev[dest] = src
        if self.goal_point is not None: 
            return self.get_path(self.goal_point, prev)
        else: 
            return dist

    def get_path(self, goal, prev):  
        global edge_num
        global used_edge
        path = [goal]
        dest = goal
        
        while prev[dest] != float("inf"): 
            used_edge[edge_num[prev[dest]][dest]] += 1
            path.append(prev[dest]) 
            dest = prev[dest]

        return list(reversed(path)) 

import sys
input = sys.stdin.readline


N,M = map(int,input().split())
route_map = [dict() for _ in range(N)]
edge_num = [dict() for _ in range(N)]
for i in range(M): 
    u, v, cost = map(int, input().split()) 
    u, v = u - 1, v - 1
    route_map[u][v] = cost 
    route_map[v][u] = cost 
    edge_num[u][v] = i 
    edge_num[v][u] = i 


used_edge = [0 for _ in range(M)]
checked_node = [[0 for _ in range(N)] for __ in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if checked_node[i][j] != 0:
            continue
        dijkstra_result1 = Dijkstra(route_map, i, j).execute()
        for k in range(len(dijkstra_result1)-1):
            for l in range(k+1,len(dijkstra_result1)):
                checked_node[dijkstra_result1[k]][dijkstra_result1[l]] += 1
        """
        dijkstra_result2 = Dijkstra(route_map, N-1-i, N-1-j).execute()
        for k in range(len(dijkstra_result2)-1):
            for l in range(k+1,len(dijkstra_result2)):
                checked_node[dijkstra_result2[k]][dijkstra_result2[l]] += 1
        """

ans = used_edge.count(0)
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
abc = [LIST() for _ in range(M)]

def warshall_floyd(d):
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = [[INF for i in range(N)] for i in range(N)] 

for x, y, z in abc:
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(N):
    d[i][i] = 0 
warshall_floyd(d)
count = 0
for a, b, c in abc:
	for i in range(N):
		if d[i][a-1] + c == d[a-1][b-1]:
			break
	else:
		count += 1
print(count)

Solution (Python):
n, m = [int(item) for item in input().split()]
abc = [[int(item) for item in input().split()] for _ in range(m)]
INF = 10 ** 9

edge = [[INF] * n for _ in range(n)]
v_edge = [[1] * n for _ in range(n)]
for a, b, c in abc:
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c

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

count = 0
for a, b, c in abc:
    if edge[a-1][b-1] != c:
        count += 1
print(count)

Solution (Python):
import copy
from scipy.sparse.csgraph import floyd_warshall as wf

N, M = map(int, input().split())
INF = float('inf')

d = [[INF] * (N) for i in range(N)]
e_list = []
for i in range(N):
    d[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c
    e_list.append([a - 1, b - 1, c])
    
wf = wf(d)

cnt = M
for a, b, c in e_list:
    for i in range(N):
        if wf[i][a] + c == wf[i][b]:
            cnt -= 1
            break
    
print(cnt)

Solution (Python):
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]: 
                    d[i][j] = d[i][k] + d[k][j]
    return d

n,w = map(int,input().split())
INF = 10**5
d = [[INF for i in range(n)] for i in range(n)]
e_list = []
for i in range(w):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
    e_list.append([x,y,z])
for i in range(n):
    d[i][i] = 0

warshall_floyd(d)
ans = w
for x,y,z in e_list:
    ok = False
    for i in range(n):
        if d[i][x] + z == d[i][y]:
            ans -= 1
            break
print(ans)

Solution (Python):
def warshall_floyd(d,route):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]: 
                    d[i][j] = d[i][k] + d[k][j]
                    route[i][j] = route[i][k] + route[k][j]
    return d

n,w = map(int,input().split())
INF = 10**5
d = [[INF for i in range(n)] for i in range(n)]
route = [[[] for i in range(n)] for i in range(n)]
for i in range(w):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
    route[x][y].append(i)
    route[y][x].append(i)
for i in range(n):
    d[i][i] = 0

warshall_floyd(d,route)
ans = w
s = set()
for i in range(n):
    for j in range(n):
        for k in route[i][j]:
            if k not in s:
                ans -= 1
                s.add(k)
print(ans)

Solution (Python):
import sys
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())

    INF = 10**6
    A = np.array([[INF for _ in range(N)] for _ in range(N)])
    for i in range(N):
        A[i][i] = 0

    edges = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        A[a][b] = c
        A[b][a] = c
        edges.append((a, b, c))

    G = floyd_warshall(A)

    ans = 0
    for a, b, c in edges:
        if G[a][b] < c:
            ans += 1

    return ans


if __name__ == '__main__':
    print(main())

Solution (Python):
N, M = map(int, input().split())

MAX = 10**10
dist = [[0 if x == i else MAX for x in range(N)] for i in range(N)]
edge_list = []
for i in range(M):
    a, b, c = map(int, input().split())
    edge = [a, b, c]
    edge_list.append(edge)
    dist[a-1][b-1] = c
    dist[b-1][a-1] = 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 = 0
for edge in edge_list:
    a, b, c = edge
    if dist[a-1][b-1] < c:
        ans += 1
print(ans)

Solution (Python):
def gen_graph(input_list):
    graph = {}

    for item in input_list:
        if not item[0] in graph:
            graph[item[0]] = {}
        if not item[1] in graph:
            graph[item[1]] = {}
        graph[item[0]][item[1]] = item[2]
        graph[item[1]][item[0]] = item[2]

    return graph


def get_lowest_cost_vertex(costs, processed):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


def get_best_routes(graph, start):
    costs = {}
    parents = {}
    processed = []

    costs[start] = 0
    parents[start] = None
    processed.append(start)

    for item in graph[start].keys():
        costs[item] = graph[start][item]
        parents[item] = start

    for item in graph.keys():
        if not (item in costs.keys() or item == start):
            costs[item] = float("inf")
            parents[item] = None

    node = get_lowest_cost_vertex(costs, processed)

    while node is not None:
        cost = costs[node]
        neighbors = graph[node]

        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node = get_lowest_cost_vertex(costs, processed)

    routes = []
    for item in graph.keys():
        if item != start:
            route = []
            route.append(item)
            parent = parents[item]
            while 1:
                route.append(parent)
                if parent == start:
                    break
                parent = parents[parent]
            route.reverse()
            routes.append(route)
    return routes


def main(vertex_count, input_list):
    graph = gen_graph(input_list)

    routes = []
    for start in range(1, vertex_count+1):
        for route in get_best_routes(graph, start):
            routes.append(route)

    route_sides = []
    for route in routes:
        for i, vertex in enumerate(route):
            if i == len(route)-1:
                break
            route_side = [route[i], route[i+1]]
            route_side_sorted = sorted(route_side)
            if not route_side_sorted in route_sides:
                route_sides.append(route_side_sorted)

    sides = []
    for item in input_list:
        side = [item[0], item[1]]
        side_sorted = sorted(side)
        sides.append(side_sorted)

    count = 0
    for side in sides:
        if not side in route_sides:
            count += 1

    return count


if __name__ == "__main__":
    input_1 = input()
    vertex_count, sides_count = list(map(int, input_1.split()))
    input_list = []
    for _ in range(sides_count):
        vertex_1, vertex_2, distance = list(map(int, input().split()))
        input_list.append((vertex_1, vertex_2, distance))
    print(main(vertex_count, input_list))

Solution (Python):
def gen_graph(input_list):
    graph = {}

    for item in input_list:
        if not item[0] in graph:
            graph[item[0]] = {}
        if not item[1] in graph:
            graph[item[1]] = {}
        graph[item[0]][item[1]] = item[2]
        graph[item[1]][item[0]] = item[2]

    return graph


def get_lowest_cost_vertex(costs, processed):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


def get_best_routes(graph, start):
    costs = {}
    parents = {}
    processed = []

    costs[start] = 0
    parents[start] = None
    processed.append(start)

    for item in graph[start].keys():
        costs[item] = graph[start][item]
        parents[item] = start

    for item in graph.keys():
        if not (item in costs.keys() or item == start):
            costs[item] = float("inf")
            parents[item] = None

    node = get_lowest_cost_vertex(costs, processed)

    while node is not None:
        cost = costs[node]
        neighbors = graph[node]

        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node = get_lowest_cost_vertex(costs, processed)

    routes = []
    for item in graph.keys():
        if item != start:
            route = []
            route.append(item)
            parent = parents[item]
            while 1:
                route.append(parent)
                if parent == start:
                    break
                parent = parents[parent]
            route.reverse()
            routes.append(route)
    return routes


def main(vertex_count, input_list):
    graph = gen_graph(input_list)

    routes = []
    for start in range(1, vertex_count+1):
        for route in get_best_routes(graph, start):
            routes.append(route)

    route_sides = []
    for route in routes:
        for i, vertex in enumerate(route):
            if i == len(route)-1:
                break
            route_side = [route[i], route[i+1]]
            route_side_sorted = sorted(route_side)
            if not route_side_sorted in route_sides:
                route_sides.append(route_side_sorted)

    sides = []
    for item in input_list:
        side = [item[0], item[1]]
        side_sorted = sorted(side)
        sides.append(side_sorted)

    count = 0
    for side in sides:
        if not side in route_sides:
            count += 1

    return count


if __name__ == "__main__":
    input_1 = input()
    vertex_count, sides_count = list(map(int, input_1.split()))
    input_list = []
    for _ in range(sides_count):
        vertex_1, vertex_2, distance = list(map(int, input().split()))
        input_list.append((vertex_1, vertex_2, distance))
    print(main(vertex_count, input_list))

Solution (Python):
def gen_graph(input_list):
    graph = {}

    for item in input_list:
        if not item[0] in graph:
            graph[item[0]] = {}
        if not item[1] in graph:
            graph[item[1]] = {}
        graph[item[0]][item[1]] = item[2]
        graph[item[1]][item[0]] = item[2]

    return graph


def get_lowest_cost_vertex(costs, processed):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node


def get_best_routes(graph, start):
    costs = {}
    parents = {}
    processed = []

    costs[start] = 0
    parents[start] = None
    processed.append(start)

    for item in graph[start].keys():
        costs[item] = graph[start][item]
        parents[item] = start

    for item in graph.keys():
        if not (item in costs.keys() or item == start):
            costs[item] = float("inf")
            parents[item] = None

    node = get_lowest_cost_vertex(costs, processed)

    while node is not None:
        cost = costs[node]
        neighbors = graph[node]

        for n in neighbors.keys():
            new_cost = cost + neighbors[n]
            if costs[n] > new_cost:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        node = get_lowest_cost_vertex(costs, processed)

    routes = []
    for item in graph.keys():
        if item != start:
            route = []
            route.append(item)
            parent = parents[item]
            while 1:
                route.append(parent)
                if parent == start:
                    break
                parent = parents[parent]
            route.reverse()
            routes.append(route)
    return routes


def main(vertex_count, input_list):
    graph = gen_graph(input_list)

    routes = []
    for start in range(1, vertex_count+1):
        for route in get_best_routes(graph, start):
            routes.append(route)

    route_sides = []
    for route in routes:
        for i, vertex in enumerate(route):
            if i == len(route)-1:
                break
            route_side = [route[i], route[i+1]]
            route_side_sorted = sorted(route_side)
            if not route_side_sorted in route_sides:
                route_sides.append(route_side_sorted)

    sides = []
    for item in input_list:
        side = [item[0], item[1]]
        side_sorted = sorted(side)
        sides.append(side_sorted)

    count = 0
    for side in sides:
        if not side in route_sides:
            count += 1

    return count


if __name__ == "__main__":
    input_1 = input()
    vertex_count, sides_count = list(map(int, input_1.split()))
    input_list = []
    for _ in range(sides_count):
        vertex_1, vertex_2, distance = list(map(int, input().split()))
        input_list.append((vertex_1, vertex_2, distance))
    print(main(vertex_count, input_list))

Solution (Python):
N, M = map(int, input().split())

A = []
B = []
C = []
for i in range(M):
    a, b, c = map(int, input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)

INF = 10**9

dist = [[INF if i != j else 0 for i in range(N)] for j in range(N)]


for i in range(M):
    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(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 i in range(M):
    
    for j in range(N):
        if dist[j][A[i]] + C[i] == dist[j][B[i]]:
            ans = ans - 1
            break

print(ans)

Solution (Python):

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

def warshall_floyd(dist,n):
    
    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])
    return dist

dist = [[float("inf") for i in range(N)] for i in range(N)] 

xyz=[]
for i in range(M):
    x,y,z = map(int,input().split())
    xyz.append([x-1,y-1,z])
    dist[x-1][y-1] = z
    dist[y-1][x-1] = z
for i in range(N):
    dist[i][i] = 0 
wf=warshall_floyd(dist,N)
ans=M
for i in range(M):
    j=0
    flag=0
    for j in range(N):
        if wf[j][xyz[i][0]] + xyz[i][2] == wf[j][xyz[i][1]]:
            flag=1
            break
    if flag == 1:
        ans-=1
    flag=0
print(ans)

Solution (Python):
from functools import reduce

def main():
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N, M = (int(_) for _ in input().split())
    d = [[1e10 for _ in range(N)] for _ in range(N)]
    a = []
    b = []
    c = []
    for i in range(M):
        ai, bi, ci = (int(_) for _ in input().split())
        d[ai-1][bi-1] = ci
        d[bi-1][ai-1] = ci
        a.append(ai-1)
        b.append(bi-1)
        c.append(ci)
        
    for i in range(N):
        d[i][i] = 0       
        
    for i in range(N):
        for j in range(N):
            for k in range(N):
                d[j][k] = min(d[j][i]+d[i][k],d[j][k])

    ans = M
    for i in range(M):
        is_shortest = False
        for j in range(N):
            if(d[j][a[i]]+c[i] == d[j][b[i]]):
                is_shortest = True
        if is_shortest:
            ans -= 1
    print(ans)
    
if __name__ == '__main__':
    main()