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):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7


def main():
    
    N, M = Scanner.map_int()

    class Edge():
        def __init__(self, a, b, c):
            self.from_ = a
            self.to_ = b
            self.cost_ = c
    edges = [] * M
    for _ in range(M):
        a, b, c = Scanner.map_int()
        a -= 1
        b -= 1
        edges.append(Edge(a, b, c))
    d = [[int(1e09) for _ in range(N)] for _ in range(N)]
    for e in edges:
        d[e.from_][e.to_] = e.cost_
        d[e.to_][e.from_] = e.cost_
    for i in range(N):
        d[i][i] = 0
    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])
    visited = [False] * M
    for s in range(N):
        for i, e in enumerate(edges):
            if d[s][e.from_] + e.cost_ == d[s][e.to_]:
                visited[i] = True
            if d[s][e.to_] + e.cost_ == d[s][e.from_]:
                visited[i] = True
    print(visited.count(False))


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

mp = [[100000 for i in range(N)] for j in range(N)]
mp2 = []
for i in range(M):
  a,b,c = map(int, input().split())
  mp[a-1][b-1] = c
  mp[b-1][a-1] = c
  mp2.append([a,b,c])
  
D = shortest_path(np.array(mp))

ans = [1 for i in range(M)]
for i,edge in enumerate(mp2):
  
  if D[edge[0]-1, edge[1]-1] >= edge[2]:
    ans[i] = 0
    
print(sum(ans))

Solution (Python):

import sys
import heapq
from collections import defaultdict
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, s, t, w):
        self.E[s].append([t, w])
        self.E[t].append([s, w])


def shortestPath(g: Graph, s: int):
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):

    g = Graph(N)
    flag = {}
    for aa, bb, cc in zip(a, b, c):
        g.add_edge(aa-1, bb-1, cc)

        if aa > bb:
            aa, bb = bb, aa
        flag[(aa-1, bb-1)] = False

    for i in range(N-1):
        dist, prev = shortestPath(g, i)

        for j, p in enumerate(prev):
            if p == None:
                continue
            a, b = p, j
            if b < a:
                a, b = j, p
            flag[(a, b)] = True
    tot = 0
    for k in flag:
        if flag[k] == False:
            tot += 1
    print(tot)
    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))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
from collections import defaultdict

def dijkstra(i, V, E, INF=1e9):
    D = [INF for v in V]
    D[i] = 0
    Q = [(d, v) for v, d in enumerate(D)]
    heapq.heapify(Q)
    prev = [None for v in V]

    while len(Q) > 0:
        du, u = heapq.heappop(Q)
        for v, (duv, *_) in E[u].items():
            dv = du + duv
            if D[v] > dv:
                D[v] = dv
                prev[v] = u
                heapq.heappush(Q, (dv, v))
    return prev

def count_path(prev, E):
    x = [(i, p) for i, p in enumerate(prev)]
    while len(x) > 0:
        i, p = x.pop()
        if p is not None:
            E[i][p][-1] += 1
            E[p][i][-1] += 1
            x.append((p, prev[p]))
    return E

n, m = map(int, input().split())
E_list = [list(map(int, input().split())) for _ in range(m)]
E = defaultdict(dict)
for j in range(m):
    a, b, c = E_list[j]
    E[a][b] = [c, 0]
    E[b][a] = [c, 0]
V = list(range(n + 1))

for i in range(1, n + 1):
    prev = dijkstra(i, V, E)
    E = count_path(prev, E)

ans = 0
for v1 in E.values():
    for v2 in v1.values():
        ans += (v2[-1] == 0)
print(ans // 2)

Solution (Python):
N,M=[int(x) for x in input().split()]
INF=1000000000000000
adj=[[INF for i in range(N+1)] for j in range(N+1)]

for i in range(N+1):
	adj[i][i]=0
	
A=[]
B=[]
C=[]
ans=M

for i in range(M):
	a,b,c=[int(x) for x in input().split()]
	adj[a][b]=min(adj[a][b],c)
	adj[b][a]=min(adj[b][a],c)
	A.append(a)
	B.append(b)
	C.append(c)

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


for i in range(M):
	temp=1
	for j in range(1,N+1):
		if adj[j][A[i]]+C[i]==adj[j][B[i]]:
			temp=0
	if temp==0:
		ans-=1
print(ans)

Solution (Python):
n,m=map(int,input().split())
inf=100000000
wf=[[inf]*n for i in range(n)]
wf_sub=[[inf]*n for i in range(n)]
for i in range(n):
    wf[i][i]=0
    wf_sub[i][i]=0
for i in range(m):
    a,b,c=map(int,input().split())
    wf[a-1][b-1]=c
    wf_sub[a-1][b-1]=c
    wf[b-1][a-1]=c
    wf_sub[b-1][a-1]=c
'''
for i in range(n):
    print(wf[i])
for i in range(n):
    print(wf_sub[i])
'''

for k in range(n):
    for i in range(n):
        for j in range(n):
            wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j])
cnt=0
for i in range(n):
    for j in range(n):
        if wf_sub[i][j]!=0 and wf_sub[i][j]!=inf:
            if wf[i][j]!=wf_sub[i][j]:
                cnt+=1

'''
for i in range(n):
    print(wf[i])
for i in range(n):
    print(wf_sub[i])
'''

print(cnt//2)

Solution (Python):
import sys
input = sys.stdin.readline
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
inf=float("inf")
n,m=map(int,input().split())
G=[[inf]*n for _ in range(n)]
for _ in range(m):
    a,b,c=map(int,input().split())
    G[a-1][b-1]=c
    G[b-1][a-1]=c

from copy import deepcopy
H=deepcopy(G)

H=warshall_floyd(H)

cnt=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if G[i][j]==inf:
            continue
        if G[i][j]!=H[i][j]:
            cnt+=1
print(cnt//2)

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split()))for i in range(m)]
dist=[[1<<29]*n for i in range(n)]
for i in range(n): dist[i][i]=0
for a in l:
  dist[a[0]-1][a[1]-1] = min(dist[a[0]-1][a[1]-1],a[2])
  dist[a[1]-1][a[0]-1] = min(dist[a[1]-1][a[0]-1],a[2])

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 in l:
  flag=False
  for j in range(n): 
    if dist[j][a[0]-1]+a[2]==dist[j][a[1]-1]: flag=True
  if flag: ans-=1
print(ans)

Solution (Python):

si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
def WF():
    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])

n,m=nm()
aa=[]
bb=[]
cc=[]
d=[[0]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    aa.append(a)
    bb.append(b)
    cc.append(c)
for i in range(n):
    for j in range(n):
        if i==j:
            d[i][j]=0
        else:
            d[i][j]=10**5

for i in range(m):
    d[aa[i]][bb[i]]=min(d[aa[i]][bb[i]],cc[i])
    d[bb[i]][aa[i]]=min(d[bb[i]][aa[i]],cc[i])
WF()

ans=m
for i in range(m):
    short=False
    for j in range(n):
        if d[j][aa[i]]+cc[i]==d[j][bb[i]]:
            short=True
    if short:
        ans-=1
print(ans)

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

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) 
rs = lambda: stdin.readline().rstrip()  

N, M = rl()
edges = [rl() for _ in range(M)]
graph = np.zeros((N, N))

for a, b, c in edges:
    graph[a-1, b-1] = c

dist = shortest_path(graph, directed=False).astype(int)
answer = 0
for a, b, c in edges:
    if c != dist[a-1, b-1]:
        answer += 1

print(answer)

Solution (Python):
import sys
from heapq import heappop, heappush


stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) 
rs = lambda: stdin.readline().rstrip()  

def dijkstra(start):
    INF = 10 ** 5
    dist = [INF] * (N+1) 
    dist[start] = 0
    que = [(0, start)]
    while que:
        
        d, v = heappop(que)
        
        if dist[v] < d:
            continue
        for next_city, cost in edges[v].items():
            
            d1 = d + cost
            
            if dist[next_city] > d1:
                dist[next_city] = d1
                heappush(que, (d1, next_city))
    return dist

N, M = rl()
INF = 10 ** 5
edges = [{} for _ in range(N+1)]
for _ in range(M):
    a, b, c = rl()
    edges[a][b] = c
    edges[b][a] = c

answer = 0
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if j not in edges[i]:
            continue
        A = dijkstra(i)
        if A[j] < edges[i][j]:
            answer += 1
            edges[i].pop(j)
            edges[j].pop(i)

print(answer)

Solution (Python):
MAX_D = 10**9
def solve():
    N,M = map(int, input().split())
    d = [[MAX_D]*N for _ in range(N)]
    edges = [[False]*N for _ in range(N)]
    base_edge = {}
    for _ in range(M):
        a,b,c = map(int, input().split())
        edges[a-1][b-1] = True
        edges[b-1][a-1] = True
        d[a-1][b-1] = c
        d[b-1][a-1] = c
        base_edge[(a-1,b-1)] = c
        base_edge[(b-1,a-1)] = c
        
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i != j and d[i][j] > d[i][k]+d[k][j]:
                    
                    edges[i][j] = False
                    if (i,k) in base_edge and base_edge[(i,k)] == d[i][k]: edges[i][k] = True
                    if (k,j) in base_edge and base_edge[(k,j)] == d[k][j]: edges[k][j] = True
                    d[i][j] = d[i][k]+d[k][j]
                    
    
    print(M - sum(map(sum, edges))//2)
    
solve()

Solution (Python):

N, M = map(int, input().split(' '))
graph = [[float('inf') for _ in range(N)] for _ in range(N)]

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


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

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

print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def warshall_floyd(N: int, graph: list) -> list:
    """ ワーシャルフロイド(頂点数, 隣接行列(0-indexed)) """
    from copy import deepcopy

    res = deepcopy(graph)
    for i in range(N):
        
        res[i][i] = 0
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    
    for i in range(N):
        if res[i][i] < 0:
            return []
    return res

N, M = MAP()
G = list2d(N, N, INF)
for i in range(M):
    a, b, c = MAP()
    a -= 1; b -= 1
    G[a][b] = c
    G[b][a] = c

wf = warshall_floyd(N, G)

cnt = 0
for i in range(N):
    for j in range(i+1, N):
        
        if G[i][j] != INF and G[i][j] > wf[i][j]:
            cnt += 1
print(cnt)

Solution (Python):
N, M = list(map(int, input().split()))
INF = 10**9
D = [[INF ]*N for _ in range(N)]
P = [[None]*N for _ in range(N)]
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    if a>b: a,b = b,a
    D[a-1][b-1] = D[b-1][a-1] = c
    P[a-1][b-1] = P[b-1][a-1] = (a-1)*N+b-1

for k in range(N):
    for i in range(N):
        for j in range(i+1, N):
            Dikj = D[i][k] + D[k][j]
            if D[i][j] > Dikj:
                D[i][j] = D[j][i] = Dikj
                P[i][j] = P[j][i] = (P[i][k], P[k][j])

E = set()
for i in range(N):
    for j in range(i+1, N):
        queue = [P[i][j]]
        while queue:
            queue_new = []
            for q in queue:
                if type(q) is tuple:
                    for x in q:
                        queue_new.append(x)
                else:
                    E.add(q)
            queue = queue_new

print(M-len(E))

Solution (Python):
N, M = map(int, input().split())
ABC = [list(map(int, input().split())) for _ in range(M)]

INF = 10 ** 15
WF = [[INF for _ in range(N + 1)] for _ in range(N + 1)]

for a, b, c in ABC:
  WF[a][b] = c
  WF[b][a] = c
for k in range(1, N + 1):
  for i in range(1, N + 1):
    for j in range(1, N + 1):
      WF[i][j] = min(WF[i][j], WF[i][k] + WF[k][j])

answer = 0
for a, b, c in ABC:
  if WF[a][b] < c:
    answer += 1
print(answer)

Solution (Python):
n,m = map(int,input().split())

import numpy as np
from scipy.sparse.csgraph import shortest_path

l = np.array([[float("inf") for i in range(n)] for j in range(n)])
from collections import defaultdict
ans = defaultdict(int)
for _ in range(m):
   a,b,c = map(int,input().split())
   l[a-1][b-1] = c
   l[b-1][a-1] = c
   if a > b:
      ans[(b,a)] = 1
   else:
      ans[(a,b)] = 1

d, p = shortest_path(l, return_predecessors=True)


for pp in p:
   for idx, ppp in enumerate(pp):
      if idx < ppp:
         ans[(idx+1,ppp+1)] = 0
      else:
         ans[(ppp+1,idx+1)] = 0
print(sum(ans.values()))

Solution (Python):
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):
    """
    ダイクストラ法 (二分ヒープ) による最短経路探索
    計算量: O((E+V)logV)
    """

    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):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:  
            path.append(node)
            node = self.prev[node]
        return path[::-1]  


N, M = map(int, input().split())
g = Graph()
visited_edges = {}
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g.add_edge(a, b, c)
    g.add_edge(b, a, c)
    visited_edges[(a, b)] = False
    visited_edges[(b, a)] = False

for i in range(N):  
    shortest = Dijkstra(g, i)
    for j in range(i+1, N):  
        paths = shortest.shortest_path(j)
        for k in range(len(paths)-1):
            visited_edges[(paths[k], paths[k+1])] = True
            visited_edges[(paths[k+1], paths[k])] = True
print(M - sum(visited_edges.values())//2)

Solution (Python):
from scipy.sparse import*
n,_,*L=map(int,open(0).read().split())
s=csgraph.floyd_warshall(csr_matrix((L[2::3],(L[::3],L[1::3])),[n+1]*2),0)
print(sum(s[f,t]<c for f,t,c in zip(*[iter(L)]*3)))

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
n,m,*L=map(int,open(0).read().split())
s=floyd_warshall(csr_matrix((L[2::3],(L[::3],L[1::3])),(n+1,n+1)),0)
ans=0
for f,t,c in zip(*[iter(L)]*3):ans+=s[f,t]<c
print(ans)

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

Solution (Python):
class DirectedEdge(object):
    def __init__(self, v, w, weight, id):
        self.v = v
        self.w = w
        self.weight = weight
        self.id = id

    def __str__(self):
        return "[{} -> {}: {}]".format(self.v, self.w, self.weight)

    def edge_from(self):
        return self.v

    def edge_to(self):
        return self.w

    def get_weight(self):
        return self.weight

    def get_id(self):
        return self.id



class EdgeWeightedDigraph(object):
    def __init__(self, vertex_size):
        self.VERTEX_SIZE = vertex_size
        self.adj = [set() for x in range(self.get_vertex_size())]

    def get_vertex_size(self):
        return self.VERTEX_SIZE

    def add_edge(self, edge):
        v = edge.edge_from()
        self.adj[v].add(edge)

    def get_adj(self, v):
        res = set()
        for edge in self.adj[v]:
            res.add(edge)
        return res


class IndexMinPQ(object):
    def __init__(self, size):
        self.keys = [None for x in range(size + 1)]  
        self.pq = [None for x in range(size + 1)]    

        self.qp = [None for x in range(size + 1)]

        self.n = 0

    def contains(self, i):
        if self.qp[i] is None:
            return False
        else:
            return True

    def is_empty(self):
        return self.n == 0

    def size(self):
        return self.n

    def decrease_key(self, i, key):
        self.keys[i] = key
        self._swim(self.qp[i])

    def insert(self, i, key):
        tail = self.n + 1
        self.pq[tail] = i
        self.qp[i] = tail
        self.keys[i] = key

        self._swim(tail)

        self.n += 1

    def _swim(self, i):
        while i != 1:
            p = self._get_parent_pos(i)
            if not self._is_less(p, i):
                self._exch(p, i)
                i = p
            else:
                break

    def del_min(self):
        head = self.pq[1]

        self.pq[1] = None
        self.keys[head] = None
        self.qp[head] = None

        self._exch(1, self.n)

        self.n -= 1
        self._sink(1)

        return head

    def _sink(self, i):
        while self._get_left_child_pos(i) <= self.n:
            left = self._get_left_child_pos(i)
            right = left + 1

            child = left
            if not left == self.n and not self._is_less(left, right):
                child = right

            if not self._is_less(i, child):
                self._exch(i, child)
                i = child
            else:
                break

    def _is_less(self, a, b):
        a_id = self.pq[a]
        b_id = self.pq[b]
        return self.keys[a_id] < self.keys[b_id]

    def _get_parent_pos(self, i):
        return i // 2

    def _get_left_child_pos(self, i):
        return i * 2

    def _exch(self, a, b):
        swap = self.pq[a]
        self.pq[a] = self.pq[b]
        self.pq[b] = swap

        if self.pq[a] is not None:
            self.qp[self.pq[a]] = a
        if self.pq[b] is not None:
            self.qp[self.pq[b]] = b


class DijkstraShortestPath(object):
    def __init__(self, edge_weighted_digraph, source):
        self.digraph = edge_weighted_digraph
        self.source = source

        self.edge_to = [None for x in range(self.digraph.get_vertex_size())]
        self.dist_to = [float("infinity") for x in range(self.digraph.get_vertex_size())]
        self.ipq = IndexMinPQ(self.digraph.get_vertex_size())

        self.dist_to[source] = 0.0
        self.ipq.insert(source, self.dist_to[source])

        while not self.ipq.is_empty():
            v = self.ipq.del_min()
            for edge in self.digraph.get_adj(v):
                self._relax(edge)

    def _relax(self, edge):
        v = edge.edge_from()
        w = edge.edge_to()
        if self.dist_to[v] + edge.get_weight() < self.dist_to[w]:
            self.dist_to[w] = self.dist_to[v] + edge.get_weight()
            self.edge_to[w] = edge

            if self.ipq.contains(w):
                self.ipq.decrease_key(w, self.dist_to[w])
            else:
                self.ipq.insert(w, self.dist_to[w])

    def has_path_to(self, v):
        return self.dist_to[v] < float("infinity")

    def path_to(self, v):
        path = []
        while self.edge_to[v] is not None:
            edge = self.edge_to[v]
            path.append(edge)
            v = edge.edge_from()
        return path


def solve():
    N, M = map(int, input().split())
    ABC = []
    for _ in range(M):
        ABC.append(tuple(map(int, input().split())))

    edges = []
    G = EdgeWeightedDigraph(N + 1)
    for a, b, c in ABC:
        edge_a = DirectedEdge(int(a), int(b), float(c), (a, b))
        edge_b = DirectedEdge(int(b), int(a), float(c), (a, b))

        G.add_edge(edge_a)
        G.add_edge(edge_b)

        edges.append((a, b))

    founds = set()
    for s in range(1, N + 1):
        sp = DijkstraShortestPath(G, s)
        for v in range(1, N + 1):
            if not v == s:
                for e in sp.path_to(v):
                    
                    founds.add(e.get_id())

    ans = len(edges) - len(founds)

    return ans


if __name__ == '__main__':
    res = solve()
    print(res)

Solution (Python):

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

d = [[float("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())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    
    e_list.append([x-1,y-1,z])
for i in range(n):
    d[i][i] = 0 
    

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 = w
for x, y, z in e_list:
    
    if d[x][y] == z:
        ans -= 1
        
print(ans)

Solution (Python):
INF = 10 ** 9

n, m = map(int, input().split())
a = [[INF] * n for _ in range(n)]
e = [None] * m
for i in range(n): a[i][i] = 0
for i in range(m):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    e[i] = (u, v, w)
    a[u][v] = w
    a[v][u] = w
for k in range(n):
    for i in range(n):
        for j in range(n):
            a[i][j] = min(a[i][j], a[i][k] + a[k][j])
c = 0
for u, v, w in e:
    if a[u][v] != w: c += 1
print(c)

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

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m = I[:2]
a, b, c = I[2:].reshape(m, 3).T
a -= 1; b -= 1
graph = np.zeros((n, n))
graph[a, b] = c

def main():
    dist = floyd_warshall(csgraph=csr_matrix(graph), directed=False)
    bl =  (dist[:, a] == dist[:, b] + c) | (dist[:, b] == dist[:, a] + c)
    res = np.any(bl, axis=0)
    ans = m - np.count_nonzero(res)
    return ans

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

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

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m = I[:2]
a, b, c = I[2:].reshape(m, 3).T
a -= 1; b -= 1
graph = np.zeros((n, n))
graph[a, b] = c

def main():
    dist = floyd_warshall(csgraph=csr_matrix(graph), directed=False)
    bl =  (dist[:, a] == dist[:, b] + c) | (dist[:, b] == dist[:, a] + c)
    res = np.any(bl, axis=0)
    ans = m - np.count_nonzero(res)
    return ans

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

Solution (Python):
import sys
from heapq import heappush, heappop

INF = 10 ** 7

n, m = map(int, sys.stdin.readline().split())
abc = map(int, sys.stdin.read().split())
abc = zip(*[abc] * 3)
graph = [[] for _ in range(n)]
for a, b, c in abc:
    graph[a-1].append((b-1, c))
    graph[b-1].append((a-1, c))

def dijkstra(v):
    used_edges = [set() for _ in range(n)]
    hq = []
    heappush(hq, (0, v, None))
    dist = [INF] * n
    parents = [set() for _ in range(n)]
    while hq:
        d, cur, prev = heappop(hq)
        if dist[cur] != INF:
            if d == dist[cur]:
                parents[cur].add(prev)
                used_edges[cur] |= used_edges[prev]
                if prev < cur:
                    used_edges[cur].add((prev, cur))
                else:
                    used_edges[cur].add((cur, prev))
            continue   
        
        dist[cur] = d
        if cur != v:
            used_edges[cur] |= used_edges[prev]
            parents[cur].add(prev)
            if prev < cur:
                used_edges[cur].add((prev, cur))
            else:
                used_edges[cur].add((cur, prev))

        for (u, c) in graph[cur]:
            if u in parents[cur] or parents[u]:
                continue
            nex = u
            heappush(hq, (d+c, nex, cur))

    res = set()
    for i in range(n):
        res |= used_edges[i]
    return res

def main():
    res = set()
    for v in range(n):
        res |= dijkstra(v)
    
    ans = m - len(res)
    return ans

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