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

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    import numpy as np    
    from scipy.sparse import csr_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    omat = csr_matrix((c, (a, b)), shape=(N+1, N+1), dtype=np.int32)
    smat = floyd_warshall(omat, directed=False)
    return ((smat-omat) < 0).sum()



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))
    print(solve(N, M, a, b, c))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

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

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=[[float("inf")]*N for i in range(N)]
A=[]
for i in range(M):
  x,y,z=map(int, input().split())
  x-=1
  y-=1
  d[x][y]=z
  d[y][x]=z
  A.append((x,y,z))
  
for i in range(N):
  d[i][i]=0 
  
D=warshall_floyd(d)

ans=0
for x,y,z in A:
  if D[x][y]!=z:
    ans+=1
print(ans)

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

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=[[float("inf")]*N for i in range(N)]
A=[]
for i in range(M):
  x,y,z=map(int, input().split())
  x-=1
  y-=1
  d[x][y]=z
  d[y][x]=z
  A.append((x,y,z))
  
for i in range(N):
  d[i][i]=0 
  
D=warshall_floyd(d)

ans=0
for x,y,z in A:
  if D[x][y]!=z:
    ans+=1
print(ans)

Solution (Python):

import sys

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    import numpy as np    
    from scipy.sparse import csr_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    omat = csr_matrix((c+c, (a+b, b+a)), shape=(N+1, N+1), dtype=np.int32)
    smat = floyd_warshall(omat)
    return ((omat-smat) > 0).sum() // 2



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))
    print(solve(N, M, a, b, c))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
from heapq import heappush,heappop
INF=10**20

def dijkstra(G, start = 0):
    d = [INF for i in range(len(G))]
    d[start] = 0
    prev = [0 for i in range(len(G))]
    
    que = []
    heappush(que, (0, start))

    while len(que) != 0:
        p = heappop(que)
        v = p[1]
        
        if d[v] < p[0]:
            continue
            
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                prev[u] = v
                heappush(que, (d[u], u))
    
    return d,prev

N,M=map(int,input().split())
G=[{} for _ in range(N+1)]

edgelist=[]
for i in range(M):
  a,b,c=map(int,input().split())
  G[a][b]=G[b][a]=c
  a,b=sorted([a,b])
  edgelist.append((a,b))
edgelist = set(edgelist)
  
shortest_edges=set()
for i in range(1,N+1):
  d,prev = dijkstra(G,i)
  for j in range(1,N+1):
    if j ==i:continue
    a,b = sorted([j,prev[j]])
    shortest_edges.add((a,b))
    
diff = edgelist.difference(shortest_edges)
print(len(diff))

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
N, M, *ABC = [int(_) for _ in open(0).read().split()]
ABC = np.array(ABC)
F = floyd_warshall(
    csr_matrix((ABC[2::3], (ABC[::3], ABC[1::3])), (N + 1, N + 1)), 0)
print(np.sum(F[ABC[::3], ABC[1::3]] != ABC[2::3]))

Solution (Python):
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]

dp = [[0 for _ in range(n)] for _ in range(n)]
INF = 10**18
for i in range(n):
    for j in range(n):
        if i!=j:
            dp[i][j] = INF
for a,b,t in l:
    dp[a-1][b-1] = t
    dp[b-1][a-1] = t



for c in range(n):
    for f in range(n):
        for la in range(n):
            dp[f][la] = min(dp[f][la] , dp[f][c] +  dp[c][la])


ans = 0
for a, b, t in l:
    cou = 0
    for j in range(n):
        for k in range(n):
            
            if dp[j][k] != dp[j][a-1] + t + dp[b-1][k]:
                cou += 1
    if cou==n**2:
        ans += 1

print(ans)

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,M = MI()


class WarshallFloyd():
    def __init__(self,N):  
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  
    def add(self,u,v,c,directed = False):
        if directed is False:  
            self.d[u][v] = c
            self.d[v][u] = c
        else:  
            self.d[u][v] = c
    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],self.d[i][k] + self.d[k][j])
        return self.d


W = WarshallFloyd(N)
edges = [0]*M
for i in range(M):
    a,b,c = MI()
    W.add(a-1,b-1,c,directed=False)
    edges[i] = (a-1,b-1,c)
for i in range(N):
    W.add(i,i,0)

W.WarshallFloyd_search()

ans = 0
for i in range(M):
    a = 0
    for j in range(N):
        if W.d[edges[i][0]][edges[i][1]] == edges[i][2]:
            a = 1
    if a == 0:
        ans += 1

print(ans)

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,M = MI()


class WarshallFloyd():
    def __init__(self,N):  
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  
    def add(self,u,v,c,directed = False):
        if directed is False:  
            self.d[u][v] = c
            self.d[v][u] = c
        else:  
            self.d[u][v] = c
    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],self.d[i][k] + self.d[k][j])
        return self.d


W = WarshallFloyd(N)
edges = [0]*M
for i in range(M):
    a,b,c = MI()
    W.add(a-1,b-1,c,directed=False)
    edges[i] = (a-1,b-1,c)
for i in range(N):
    W.add(i,i,0)

W.WarshallFloyd_search()

ans = 0
for i in range(M):
    a = 0
    for j in range(N):
        if W.d[j][edges[i][1]] == W.d[j][edges[i][0]] + edges[i][2]:
            a = 1
    if a == 0:
        ans += 1

print(ans)

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N,M = MI()


class WarshallFloyd():
    def __init__(self,N):  
        self.N = N
        self.d = [[float('inf')]*N for i in range(N)]  
    def add(self,u,v,c,directed = False):
        if directed is False:  
            self.d[u][v] = c
            self.d[v][u] = c
        else:  
            self.d[u][v] = c
    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j],self.d[i][k] + self.d[k][j])
        return self.d


W = WarshallFloyd(N)
edges = [0]*M
for i in range(M):
    a,b,c = MI()
    W.add(a-1,b-1,c,directed=False)
    edges[i] = (a-1,b-1,c)
for i in range(N):
    W.add(i,i,0)

W.WarshallFloyd_search()

ans = 0
for i in range(M):
    a = 0
    for j in range(N):
        for k in range(N):
            if W.d[j][k] == W.d[j][edges[i][0]] + edges[i][2] + W.d[edges[i][1]][k]:
                a = 1
    if a == 0:
        ans += 1

print(ans)

Solution (Python):
import heapq
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    g[a-1].append((b-1,c))
    g[b-1].append((a-1,c))
vs = [[False]*n for _ in range(n)]
for i in range(n):
    ds = [-1]*n
    hq = [(0,i,None)]
    while hq:
        c,idx,v = heapq.heappop(hq)
        if ds[idx] != -1:
            if ds[idx] == c:
                vs[v[0]][v[1]] = True
            continue
        ds[idx] = c
        if v != None:
            vs[v[0]][v[1]] = True
        for j in g[idx]:
            if ds[j[0]] == -1:
                heapq.heappush(hq,(c+j[1],j[0],(idx,j[0])))
            elif ds[j[0]] == c+j[1]:
                vs[idx][j[0]] = True
res = 0
for i in range(n):
    for j in g[i]:
        if vs[i][j[0]] == False:
            res += 1
print(res//2)

Solution (Python):
n, m = map(int, input().split())
graph = [[float('inf')]*n for i in range(n)]
u_s=[]
v_s=[]
w_s=[]
for _ in range(m):
    u, v, w = map(int, input().split())
    u_s.append(u-1)
    v_s.append(v-1)
    w_s.append(w)
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0


def warshall_floyd(adj_m):
    
    _dist=adj_m
    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=warshall_floyd(graph)

ans=0
for i in range(m):
    if w_s[i]>dist[u_s[i]][v_s[i]]:
        ans+=1

print(ans)

Solution (Python):
n, m = map(int, input().split())
graph = [[float('inf')]*n for i in range(n)]
u_s=[]
v_s=[]
w_s=[]
for _ in range(m):
    u, v, w = map(int, input().split())
    u_s.append(u-1)
    v_s.append(v-1)
    w_s.append(w)
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0


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

dist=warshall_floyd(graph)

ans=0
for i in range(m):
    if w_s[i]>dist[u_s[i]][v_s[i]]:
        ans+=1

print(ans)

Solution (Python):
from collections import defaultdict as dd

N,M = map(int,input().split())
check = dd(int)
edge = []
res = 0
dist = [[10**18]*N for _ in range(N)]
for i in range(M):
    p,q,c = map(int,input().split())
    dist[p-1][q-1] = c
    dist[q-1][p-1] = c
    edge.append((p-1,q-1,c))
    check[(max(p-1,q-1),min(p-1,q-1))] = 1
for i in range(N):
    dist[i][i] = 0

for i in range(N):
    for j in range(N):
        for k in range(N):
            if dist[j][k] > dist[j][i]+dist[i][k]:
                dist[j][k] = dist[j][i] + dist[i][k]

for now in edge:
    for s in range(N):
        for t in range(N):
            if dist[s][t] == dist[s][now[0]] + now[2] + dist[now[1]][t]:
                check[(max(now[0],now[1]),min(now[0],now[1]))] = 0
for v in check.items():
    res += v[1]
    
print(res)

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

A = []
B = []
C = []

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

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

print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *ABC = map(int, read().split())
    G = [[INF] * N for _ in range(N)]
    edge = [0] * M
    for i, (a, b, c) in enumerate(zip(*[iter(ABC)] * 3)):
        edge[i] = (a - 1, b - 1, c)
        G[a - 1][b - 1] = G[b - 1][a - 1] = c
    for i in range(N):
        G[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *ABC = map(int, read().split())
    G = [[INF] * N for _ in range(N)]
    edge = [0] * M
    for i, (a, b, c) in enumerate(zip(*[iter(ABC)] * 3)):
        edge[i] = (a - 1, b - 1, c)
        G[a - 1][b - 1] = G[b - 1][a - 1] = c
    for i in range(N):
        G[i][i] = 0

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]

    ans = 0
    for a, b, c in edge:
        used = False
        for i in range(N):
            if G[i][b] == G[i][a] + c or G[i][a] == G[i][b] + c:
                used = True
                break
        if not used:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for i, (a, b, c) in enumerate(zip(*[iter(AB)] * 3)):
        G[a - 1].append((b - 1, c, i))
        G[b - 1].append((a - 1, c, i))

    vec = [False] * M
    for i in range(N):
        dist = [INF] * N
        dist[i] = 0
        from_edge = [[] for _ in range(N)]
        hq = [(0, i)]

        while hq:
            d, v = heappop(hq)
            if dist[v] < d:
                continue
            for nv, cost, edge in G[v]:
                if dist[nv] > d + cost:
                    dist[nv] = d + cost
                    heappush(hq, (dist[nv], nv))
                    from_edge[nv] = [edge]
                elif dist[nv] == d + cost:
                    from_edge[nv].append(edge)

        for edges in from_edge:
            for e in edges:
                vec[e] = True

    ans = sum(1 for flag in vec if not flag)
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
from copy import deepcopy
INF = 1 << 32
n, m = map(int, input().split())
d = [[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
    d[a][b] = c
    d[b][a] = c 
for i in range(n):
    d[i][i] = 0

dist = deepcopy(d)

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])
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if d[i][j] < INF and d[i][j] != dist[i][j]:
            cnt += 1
print(cnt)

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

N,M=map(int,input().split())
G= [[0]*(N+1) for _ in range(N+1)]
abc = [list(map(int,input().split())) for _ in range(M)]

for a, b, c in abc:
  G[a][b] = c
  G[b][a] = c

cost = floyd_warshall(csr_matrix(G))
cnt = 0
for a, b, c in abc:
  if cost[a][b] < c:
    cnt += 1
print(cnt)

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

    n,m=map(int, input().split())
    edge = [[] for _ in range(n)]
    d = [[float("inf")]*n for i in range(n)]
    d_1 = [[float("inf")]*n for i in range(n)]
    e_lis = [0]*m
    for i in range(m):
        a,b,c=map(int, input().split())
        d[a-1][b-1]=d[b-1][a-1]=d_1[a-1][b-1]=d_1[b-1][a-1]=c
    res = warshall_floyd(d,n)
    cnt=0
    for i in range(n):
        for j in range(n):
            if(res[i][j]!=d_1[i][j] and d_1[i][j]<10000):
                cnt+=1
    print(cnt//2)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq

n,m = map(int,input().split())
abc = [list(map(int,input().split())) for _ in range(m)]

edges = [[] for _ in range(n)]
for a,b,dis in abc:
    edges[a-1].append((b-1, dis))
    edges[b-1].append((a-1, dis))

def dijkstra(edges, s):
    hq = []
    d = [-1] * n
    d[s] = 0
    heapq.heappush(hq, (0, s))
    while hq:
        d1, p = heapq.heappop(hq)
        for p2, d2 in edges[p]:
            if d[p2] == -1 or d[p2] > d1 + d2:
                d[p2] = d1 + d2
                heapq.heappush(hq, (d1+d2, p2))
    return d

d = []

for i in range(n):
    d.append(dijkstra(edges, i))

ans = 0

for a,b,dis in abc:
    if dis > d[a-1][b-1]:
        ans += 1

print(ans)

Solution (Python):
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
 
 
n,w = map(int,input().split()) 
 
d = [[float("inf")]*n for i in range(n)]

E = [tuple(map(int, input().split())) for _ in range(w)]


for x,y,z in E:
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 

root = warshall_floyd(d)

ans = 0

for x,y,z in E:
    if d[x-1][y-1] != z:
        ans += 1
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial, gcd
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  
import sys  

from collections import defaultdict, deque
from heapq import heappush, heappop

class DiGraph:
    def __init__(self, n, edges, weight=False):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.reverse_adj = [[] for _ in range(n)]
        self.degree = [0] * n
        self.weight = defaultdict(lambda: 10**18)
        if weight:
            for u, v, weight in edges:
                self.adj[u].append(v)
                self.reverse_adj[v].append(u)
                self.degree[v] += 1
                self.weight[(u, v)] = weight
        else:
            for u, v in edges:
                self.adj[u].append(v)
                self.reverse_adj[v].append(u)
                self.degree[v] += 1
                self.weight[(u, v)] = 1

    def dijkstra(self, start, goal=None):  
        INF = 10**18
        dist = [INF] * self.n
        dist[start] = 0
        heap = [(0, start)]  
        sp_prev = [None] * self.n  
        while heap:
            dist_v, v = heappop(heap)
            if dist[v] < dist_v:
                continue
            for adj in self.adj[v]:
                edge_weight = self.weight[(v, adj)]
                if dist[v] + edge_weight < dist[adj]:
                    dist[adj] = dist[v] + edge_weight
                    sp_prev[adj] = v
                    heappush(heap, (dist[adj], adj))

        if goal is not None:
            if dist[goal] == INF:
                return dist, []
            else:
                path = [goal]
                v = goal
                while v != start:
                    v = sp_prev[v]
                    path.append(v)
                path.reverse()
                return dist, path
        else:
            return dist, sp_prev

    def scc_decompose(self):  
        used = [False] * self.n
        order = []  
        for i in range(self.n):
            if not used[i]:
                stack = [i]
                used[i] = True
                while stack:
                    u = stack.pop()
                    u_movable = False
                    for v in self.adj[u]:  
                        if not used[v]:
                            u_movable = True
                            used[v] = True
                            stack.append(u)
                            stack.append(v)
                            break
                    if not u_movable:
                        order.append(u)

        used = [False] * self.n
        group = [None] * self.n
        label = 0
        for v in reversed(order):
            if not used[v]:
                stack = [v]
                group[v] = label
                while stack:
                    v = stack.pop()
                    used[v] = True
                    for u in self.reverse_adj[v]:  
                        if not used[u]:
                            group[u] = label
                            stack.append(u)
                label += 1

        
        reduction_graph = [[] for _ in range(len(set(group)))]
        reduction_components = [[] for _ in range(len(set(group)))]
        for u in range(self.n):
            for v in self.adj[u]:  
                if group[u] == group[v]:
                    continue
                reduction_graph[group[u]].append(group[v])
            reduction_components[group[u]].append(u)
        return reduction_graph, reduction_components, group



def topological_sort(DAG):  
    n = len(DAG)
    degree = [0] * n
    for u in range(n):
        for v in DAG[u]:  
            degree[v] += 1
    ret = [i for i in range(n) if degree[i] == 0]
    queue = deque(ret)
    while queue:
        u = queue.popleft()
        for v in DAG[u]:
            degree[v] -= 1
            if degree[v] == 0:
                queue.append(v)
                ret.append(v)
    return ret



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

G = DiGraph(n, edges, weight=True)
ANS = set()
for u, v in combinations(range(n), 2):
    _, path = G.dijkstra(u, v)
    for a, b in zip(path[:], path[1:]):
        ANS.add((a, b))

ans = 0
for a, b, _ in edges:
    if (a, b) in ANS or (b, a) in ANS:
        continue
    else:
        ans += 1
print(ans//2)

Solution (Python):
n,m=map(int,input().split())
INF=10**18
e=[[INF for _ in range(n)]for _ in range(n)]
d=[]
for i in range(m):
  a,b,c=map(int,input().split())
  e[a-1][b-1]=c
  e[b-1][a-1]=c
  d.append((a-1,b-1,c))
for k in range(n):
  for i in range(n):
    for j in range(n):
      e[i][j]=min(e[i][j],e[i][k]+e[k][j])
ans=0
for i,j,k in d:
  if e[i][j]!=k:ans+=1
print(ans)

Solution (Python):
N,M=map(int,input().split())
graph=[[] for _ in range(N)]
cost=[[float("inf")]*N for _ in range(N)]
for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1][b-1]=c
    cost[b-1][a-1]=c

def dijkstra(S,N,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[S]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

dist=[]
for s in range(N):
    dist.append(dijkstra(s,N,cost))

checked=[[False]*N for _ in range(N)]
ans=M
for s in range(N):
    for i in range(s,N):
        for j in graph[i]:
            if checked[i][j]:
                continue
            
            if dist[s][i]+cost[i][j]==dist[s][j]:
                ans-=1
                checked[i][j]=True
                checked[j][i]=True
print(ans)

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

def main():
  n, m = map(int, input().split())
  road = [[100000]*n for _ in range(n)]
  count = [[-1]*n for i in range(n)]
  for _ in range(m):
    a, b, c = map(int, input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
    count[a-1][b-1] = 0
    count[b-1][a-1] = 0
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if road[i][k]+road[k][j] < road[i][j]:
          if count[i][j] == 0:
            count[i][j] = 1
          road[i][j] = road[i][k]+road[k][j]
  ans = 0
  for i in range(n):
    ans += count[i].count(1)
  print(ans//2)
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):
              
                d[i][j] = min(d[i][k] + d[k][j], d[i][j])
                
        
    return d


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

d = [[float("INF")] * n for i in range(n)]


hen = [0] * m
for i in range(m):
    x,y,z = map(int,input().split())
    d[x - 1][y - 1] = z
    d[y - 1][x - 1] = z
    hen[i] = [x - 1, y - 1, z]
for i in range(n):
    d[i][i] = 0 

ans = warshall_floyd(d)



answer = 0
for i in range(m):
  now = hen[i]
  if d[now[0]][now[1]] != now[2]:
    answer += 1
  
print(answer)

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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


n,w = map(int,input().split()) 
edge=[]
d = [[float("inf")]*n for i in range(n)]

for i in range(w):
    x,y,z = map(int,input().split())
    x-=1
    y-=1
    edge.append([x,y,z])
    d[x][y] = z
    d[y][x] = z
for i in range(n):
    d[i][i] = 0 
warshall_floyd(d)

count=0
for x,y,z in edge:
    flag=True
    for i in range(n):
        for j in range(n):
            if d[i][j]==d[i][x]+z+d[y][j]:
                
                flag=False
    if flag==True:
        count+=1
print(count)

Solution (Python):
N,M=map(int,input().split())
a,b,c=0,0,0
E=[]
INF=10**12
D=[[INF]*N for i in range(N)]
for i in range(N):
  D[i][i]=0
for i in range(M):
  a,b,c=map(int,input().split())
  a,b=a-1,b-1
  D[a][b]=c
  D[b][a]=c
  E.append((a,b,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])
P=0
for i in range(M):
  if D[E[i][0]][E[i][1]]!=E[i][2]:
    P+=1
print(P)

Solution (Python):
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

import numpy as np
from scipy.sparse import *

N, M = ri_()
a = [0] * M
b = [0] * M
c = [0] * M
for i in range(M):
    ai, bi, ci = ri_()
    a[i], b[i], c[i] = ai - 1, bi - 1, ci
G = csr_matrix((c, (a, b)), shape=(N, N))
d = csgraph.floyd_warshall(G, directed=False)
ans = 0
for i in range(M):
    if d[a[i], b[i]] != c[i]:
        ans += 1
print(ans)

Solution (Python):
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    dist = [
        [math.inf]*N for _ in range(N)
    ]

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

    A, B, C = [], [], []
    for _ in range(M):
        a, b, c = read_ints()
        a -= 1
        b -= 1
        A.append(a)
        B.append(b)
        C.append(c)
        dist[a][b] = 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][k]+dist[k][j], dist[i][j])

    count = M
    for i in range(M):
        is_shortest = False
        for j in range(N):
            if dist[j][A[i]] == dist[j][B[i]]+C[i]:
                is_shortest = True
        if is_shortest:
            count -= 1
    return count


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

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

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

a = []

d = [[10 ** 10] * n for i in range(n)]
k = [n for i in range(n)]

for i in range(w):
    x,y,z = map(int,input().split(" "))
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    a.append([x,y,z])
for i in range(n):
    d[i][i] = 0

d = warshall_floyd(d)

ans = w
for i in range(len(a)):
    for s in range(n):
        if d[s][a[i][1]-1] + a[i][2] == d[s][a[i][0]-1]:
            ans -= 1
            break

print(ans)