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):
class WarshallFloyd:
    def __init__(self,V,inf):
        self.V=V
        self.inf=inf
        self.G=[[inf]*V for _ in range(V)]
        for i in range(V):
            self.G[i][i]=0

    def add(self,u,v,cost):
        self.G[u][v]=min(self.G[u][v],cost)

    def shortest_path(self):
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    self.G[i][j]=min(self.G[i][j],self.G[i][k]+self.G[k][j])
        return self.G

    def exist_negative_loop(self):
        for i in range(self.V):
            if self.G[i][i]<0:
                return True
        return False

from sys import stdin
def main():
    
    readline=stdin.readline
    inf=10**9
    n,m=map(int,readline().split())
    wf=WarshallFloyd(n,inf)
    a=[0]*m
    b=[0]*m
    c=[0]*m
    for i in range(m):
        a[i],b[i],c[i]=map(int,readline().split())
        a[i]-=1
        b[i]-=1
        wf.add(a[i],b[i],c[i])
        wf.add(b[i],a[i],c[i])

    li=wf.shortest_path()

    flags=[False]*m
    for i in range(m):
        v=a[i]
        u=b[i]
        w=c[i]
        for j in range(n):
            for k in range(n):
                if li[j][v]+w+li[u][k]==li[j][k]:
                    flags[i]=True

    print(len([i for i in range(m) if flags[i]==False]))

if __name__=="__main__":
    main()

Solution (Python):
n,w = map(int,input().split()) 
from collections import defaultdict
D=defaultdict(list)
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]
                    D[(i,j)]=D[(i,k)]+D[(k,j)][1:]
    return d
done=[[-1]*n for _ in range(n)]
d = [[float("inf")]*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
    D[(x-1,y-1)]=[x-1,y-1]
    D[(y-1,x-1)]=[y-1,x-1]
    done[x-1][y-1]=0
    done[y-1][x-1]=0
for i in range(n):
    d[i][i] = 0 
warshall_floyd(d)
for l in D.values():
    for i in range(1,len(l)):
        a=l[i-1]
        b=l[i]
        done[a][b]=1
        done[b][a]=1
import numpy as np
done=np.array(done)
ans=(done==0).sum()


print(ans//2)

Solution (Python):
import heapq
N,M = map(int,input().split())
INF = float("inf")
edge = [[] for _ in range(N)]


List = [] 
for i in range(M):
  a,b,c = map(int,input().split())
  a-=1;b-=1
  edge[a].append([c,b,i])
  edge[b].append([c,a,i])
  List.append([c,a,b,i])

def dijkstra_heap(s):
  d = [INF for _ in range(N)]
  used = [True for _ in range(N)]
  d[s] = 0
  used[s] = False
  edgelist=[]
  for e in edge[s]:
    heapq.heappush(edgelist,e)
  while len(edgelist):
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]: 
      continue
    v = minedge[1]
    d[v] = minedge[0]
    
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,[e[0]+d[v],e[1],e[2]])
  return d

L = set([])
for i in range(N):
  dist = dijkstra_heap(i)
  for c, s, g, ID in List: 
    if dist[s] + c == dist[g]:
      L.add(ID)
ans = M -len(L)
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

def modify(x,y):
    if x>y:
        x,y = y,x
    return (x,y)


edge = [[] for _ in range(N)]
edgeid = dict()
for k in range(M):
    u,v,r = map(int,input().split())
    edge[u-1].append((v-1, r))
    edge[v-1].append((u-1, r))
    edgeid[modify(u-1,v-1)] = k

from heapq import heappop,heappush, heapify
INF = 10**20
def dijkstra2(S, N, Edge):
    
    
    
    

    dist = [INF]*N
    dist[S] = 0
    root = [-1]*N
    que = [(0, S)]
    heapify(que)
    
    while que:
        c, v = heappop(que)
        if dist[v] < c: continue

        for nv, nc in Edge[v]:
            if c+nc < dist[nv]:
                dist[nv] = c+nc
                root[nv] = v
                heappush(que, (c+nc, nv))
    
    return [dist, root]

def find_path(S,T,root):
    
    path = []
    cur = T
    while cur!=S:
        past = root[cur]
        path.append((past, cur))
        cur = past
    return path

unused_flag = [True] * M
for start in range(N):
    dist, root = dijkstra2(start, N, edge)
    for goal in range(N):
        if start==goal:continue
        for p in find_path(start, goal, root):
            unused_flag[edgeid[modify(p[0],p[1])]] = False

print(sum(unused_flag))

Solution (Python):
n, m = map(int, input().split())
INF = 10**10
d = [[INF]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
nxt = [[[i] for i in range(n)] for _ in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            if d[i][k]+d[k][j] < d[i][j]:
                d[i][j] = d[i][k]+d[k][j]
                nxt[i][j] = nxt[i][k][:]
            elif d[i][k]+d[k][j] == d[i][j]:
                nxt[i][j] += nxt[i][k]
s = set()
for start in range(n):
    for goal in range(n):
        if start==goal:
            continue
        def DFS(i):
            for j in nxt[i][goal]:
                s.add((i, j))
                if j!=goal:
                    DFS(j)
        DFS(start)
print(m-len(s)//2)

Solution (Python):
import sys
import heapq
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def dijkstra_heap(s):
        d = [f_inf] * n
        used = [True] * n
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist, e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, [e[0] + d[v], e[1]])
        return d

    used = set()
    for i in range(n):
        dist = dijkstra_heap(i)
        for d, to, fr in k:
            if dist[to] + d == dist[fr]:
                used.add((to, fr))

    print(len(k) - len(used))

if __name__ == '__main__':
    resolve()

Solution (Python):
import heapq
INFTY = 10**6
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
Arc = {}
for _ in range(M):
    a,b,c = map(int,input().split())
    G[a].append((b,c))
    G[b].append((a,c))
    Arc[(a,b)]=0
    Arc[(b,a)]=0
for s in range(1,N+1):
    dist = [INFTY for _ in range(N+1)]
    dist[s] = 0
    hist = [0 for _ in range(N+1)]
    heap = [(0,s)]
    pre = {}
    while heap:
        d,x = heapq.heappop(heap)
        if dist[x]<d:continue
        hist[x] = 1
        for y,e in G[x]:
            if hist[y]==0 and dist[y]>d+e:
                dist[y] = d+e
                pre[y] = x
                heapq.heappush(heap,(d+e,y))
    for j in pre:
        a = j
        while pre[a]!=s:
            b = pre[a]
            Arc[(a,b)] = 1
            Arc[(b,a)] = 1
            a = b
        Arc[(a,s)] = 1
        Arc[(s,a)] = 1
cnt = 0
for x in Arc:
    if Arc[x]==0:
        cnt += 1
print(cnt//2)

Solution (Python):
N, M = map(int, input().split())
INF = 10**18

minDist = [[INF] * N for _ in range(N)]
for i in range(N):
    minDist[i][i] = 0

edges = []
for _ in range(M):
    fr, to, d = map(int, input().split())
    fr -= 1
    to -= 1
    edges.append((fr, to, d))
    minDist[fr][to] = d
    minDist[to][fr] = d

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

ans = 0
for fr, to, d in edges:
    if minDist[fr][to] < d:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int, input().split())
inf = 10**8
d = [[inf]*N for _ in range(N)]
E = [[] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    E[a-1].append((b-1, c))

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

cnt = 0
for i in range(N):
    for e in E[i]:
        j = e[0]
        c = e[1]
        flag = False
        for k in range(N):
            for l in range(k+1, N):
                if d[k][l] == d[k][i]+c+d[j][l] or d[k][l] == d[k][j]+c+d[i][l]:
                    cnt += 1
                    flag = True
                    break
            if flag:
                break
print(M-cnt)

Solution (Python):




import sys
readline = sys.stdin.readline

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

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

INF = 10 ** 9
G = [[INF] * N for i in range(N)]
for i in range(M):
  a,b,c = map(int,readline().split())
  G[a-1][b-1] = c
  G[b-1][a-1] = c

d = csgraph_from_dense(G, null_value=10**9)
d = floyd_warshall(d)

ans = 0
for a in range(N-1):
  for b in range(a + 1,N):
    if G[a][b] == INF:
      continue
    if G[a][b] > d[a][b]:
      ans += 1
      
print(ans)

Solution (Python):
N, M = map(int, input().split())
d = [[1000000]*N for _ in range(N)]
d_dict = {}

inf = 0
for i in range(M):
  a, b, c = map(int, input().split())
  d[a-1][b-1] = c
  d[b-1][a-1] = c
  d_dict[(a-1, b-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 = 0
for key in d_dict:
  if d[key[0]][key[1]] < d_dict[key]:
    ans += 1
    
print(ans)

Solution (Python):
import heapq
n, m = map( int, input().split() )
adj_list = [ [] for i in range( n+1 ) ]
for _ in range( m ):
    a, b, c = map( int, input().split() )
    adj_list[ a ].append( ( b, c ) )
    adj_list[ b ].append( ( a, c ) )


def dijkstra( start ):
    prev_node = [ -1 ] * ( n + 1 )
    INF = 10 ** 10
    VISITED = 1
    NOT_VISITED = 0
    cost = [ INF ] * ( n + 1 )
    cost[ start ] = 0
    visit = [ NOT_VISITED ] * ( n + 1 )
    queue = [ ( cost[ start ], start ) ]
    while len( queue ) > 0:
        c, v = heapq.heappop( queue )
        visit[ v ] = VISITED
        for u, cost_vu in adj_list[v]:
            if visit[ u ] == VISITED:
                continue
            if cost[u] > cost[v] + cost_vu:
                cost[u] = cost[v] + cost_vu
                heapq.heappush( queue, ( cost[u], u ) )
                prev_node[ u ] = v
    return prev_node

used_edge = [ [ False ] * ( n+1 ) for i in range( n+1 ) ]

used_count = 0
for s in range( 1, n+1 ):
    prev_node = dijkstra( s )
    for i in range( 1, n+1 ):
        j = prev_node[ i ]
        if j == -1:
            continue
        if used_edge[ i ][ j ] == False:
            used_count += 1
            used_edge[ i ][ j ] = True
            used_edge[ j ][ i ] = True

print( m - used_count )

Solution (Python):
N,M = map(int,input().split())
from collections import deque
v = [deque([]) for _ in range(N)]

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

s = deque([])
for i in range(N):
    ls = [[-1,M*10000]]*N
    ls[i] =  [-1,0]
    q = [deque(j for j in k) for k in v]
    l = deque([i])
    while l:
        u = l.popleft()
        x = len(q[u])
        for i in range(x):
            e = q[u].popleft()
            if ls[u][1] + e[1] < ls[e[0]][1]:
                ls[e[0]] = [u, ls[u][1] + e[1]]
                l.append(e[0])
            q[u].append(e)
    for j,e in enumerate(ls):
        if e[0] != -1:
             s.append([min(j,e[0]),max(j,e[0])])

s = list(map(list, set(map(tuple, s))))
print(M-len(s))

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

def dijkstra(G,s,n):
    que=[(0,s)]
    dist=[INF]*n
    last=[-1]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        for c,v in G[u]:
            if(dist[u]+c<dist[v]):
                dist[v]=dist[u]+c
                last[v]=u
                heappush(que,(dist[v],v))
    return dist,last

dic={}
N,M=map(int,input().split())
G=[[] for i in range(N)]
Edges=[]
for i in range(M):
    a,b,c=map(int,input().split())
    a-=1;b-=1
    G[a].append((c,b))
    G[b].append((c,a))
    Edges.append(tuple(sorted([a,b])))

for i in range(N):
    dist,last=dijkstra(G,i,N)
    for j in range(i):
        now=j
        while(now!=i):
            nex=last[now]
            dic[tuple(sorted([now,nex]))]=1
            now=nex
ans=len(Edges)
for u,v in Edges:
    if (u,v) in dic:
        ans-=1
print(ans)

Solution (Python):
import heapq
from collections import deque
N,M=map(int,input().split())
table=[[float("inf") for _ in range(N)] for _ in range(N)]
used=[[-float("inf") for _ in range(N)] for _ in range(N)]
tree=[[] for _ in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    used[a-1][b-1]=0
    used[b-1][a-1]=0
for i in range(N):
    table[i][i]=0

for i in range(N):
    d=[float("inf") for _ in range(N)]
    d[i]=0
    q=[]
    prev=[-1]*N
    q.append([0,i])
    heapq.heapify(q)
    while len(q)>0:
        dist,u=heapq.heappop(q)
        if d[u]<dist: continue
        piv=prev[u]
        v=u
        while piv!=-1:
            
            used[piv][v] = 1
            used[v][piv] = 1
            v = piv
            piv=prev[piv]
        for i in tree[u]:
            alt=d[u]+table[u][i]
            if d[i]>alt:
                d[i]=alt
                heapq.heappush(q,[alt,i])
                prev[i]=u
        
        
    

ans=0
for i in range(N):
    for j in range(N):
        if used[i][j]==0:
            ans=ans+1
print(ans//2)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True




def warshall_floyd(d, n):
    
    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



def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)






def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



n, m = map(int, input().split())
d = [[INF for j in range(n)] for i in range(n)]
x = []
for i in range(m):
    a, b, c = map(int, input().split())
    x.append([a - 1, b - 1, c])
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c
d2 = warshall_floyd(d, n)

ans = 0
for i in x:
    if d2[i[0]][i[1]] != i[2]:
        ans += 1
print(ans)

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

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

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

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

dist = floyd_warshall(edge)

ans = 0

for a,b,c in abc:
    if dist[a-1][b-1] != c:
        ans += 1

print(ans)

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())
ma = [[0]*n for _ in range(n)]
list_ABC = [ list(map(int,input().split(" "))) for i in range(m)]

for a, b, c in list_ABC:
  ma[a-1][b-1] = c
  ma[b-1][a-1] = c
  
y = dijkstra(ma, directed=False).astype(int)
 
ans = 0
 
for a, b, c in list_ABC:
  if y[a-1][b-1] != c:
    ans += 1
    
print(ans)

Solution (Python):


import sys

















from heapq import heapify, heappush, heappop 












def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    class PQueueMin:
        def __init__(self):
            self.pq = []    
        
        def push(self, ind, cost):
            heappush(self.pq, [cost, ind])
        
        def pop(self):
            cost, ind = heappop(self.pq)
            return [ind, cost]
    
        def is_empty(self):
            return len(self.pq)==0
    
    
    
    def dijkstra(adj_with_weight, start):
        '''
        Dijkstra 法 O((E+V)lgV) (頂点を回るときに最小のものを取り出していくのに VlgV, cost の更新で ElgV)
        負辺を含まぬ重みつきグラフについて、ある頂点から他の頂点までの最短コストを貪欲に計算する
        '''
        V = len(adj_with_weight)
        cost = [float('inf')] * V
        previous = [None] * V
        cost[start] = 0
        fixed = [False] * V
        pq = PQueueMin()
        
        pq.push(start, cost[start])
        while not pq.is_empty():
            
            u, cost_of_u = pq.pop()
            fixed[u] = True
            for v, weight_of_uv in adj_with_weight[u]:
                if not fixed[v] and cost[v] > cost_of_u + weight_of_uv:
                    cost[v] = cost_of_u + weight_of_uv
                    previous[v] = u
                    pq.push(v, cost[v])
        return cost, previous
    
    n, m = mi()
    adj_with_weight = [[] for _ in range(n)]
    edge_matrix = [[False] * n for _ in range(n)]    
    for _ in range(m):
        a, b, c = mi()
        a -= 1
        b -= 1
        adj_with_weight[a].append((b, c))
        adj_with_weight[b].append((a, c))
    
    for i in range(n):
        _, previous = dijkstra(adj_with_weight, i)
        
        for j in range(n):
            if j != i:
                u = previous[j]
                j, u = min(j, u), max(j, u)
                edge_matrix[j][u] = True
    
    
    cnt = 0
    for u in range(n):
        for v, _ in adj_with_weight[u]:
            if u < v and not edge_matrix[u][v]:
                cnt += 1
    print(cnt)
    

    



if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline









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

g = [[0 for _ in range(N)] for _ in range(N)]

for a,b,c in ABC:
    g[a-1][b-1] = c

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
csg = csgraph_from_dense(g)
d = floyd_warshall(csg, directed=False)

ans = 0
for a,b,c in ABC:
    if c != d[a-1][b-1]:
        ans += 1

print(ans)

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

INF = 10**10


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

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

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 e in edge:
    flag = False
    i, j, c = e
    for s in range(n):
        if flag:
            break
        for t in range(n):
            if dist[s][i]+c+dist[j][t] == dist[s][t]:
                flag = True
                break
    if flag:
        ans -= 1
print(ans)

Solution (Python):
import sys
import bisect

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7



def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class UF:
    def __init__(self, N):
        self.state = [-1] * N
        self.rank = [0] * N
        self.num_group = N

    def get_parent(self, a):
        p = self.state[a]
        if p < 0:
            return a

        q = self.get_parent(p)
        self.state[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return

        if self.rank[pa] > self.rank[pb]:
            pa, pb = pb, pa
            a, b = b, a
        elif self.rank[pa] == self.rank[pb]:
            self.rank[pb] += 1

        self.state[pb] += self.state[pa]
        self.state[pa] = pb
        self.state[a] = pb
        self.num_group -= 1

    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def get_size(self, a):
        return -self.state[self.get_parent(a)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, M = read_values()
    L = []
    D = [[10 ** 10 for _ in range(N)] for __ in range(N)]
    for _ in range(M):
        a, b, c = read_values()
        a -= 1
        b -= 1
        D[a][b] = c
        D[b][a] = c
        L.append((c, a, b))
    L.sort()

    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])
    res = 0
    for c, a, b in L:
        if D[a][b] < c:
            res += 1

    print(res)


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())
ma = [[0]*n for _ in range(n)]
list_ABC = [ list(map(int,input().split(" "))) for i in range(m)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

x = csr_matrix(ma)
y = dijkstra(x, directed=False).astype(int)

ans = 0

for a, b, c in list_ABC:
  if y[a-1][b-1] != c:
      ans += 1

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    d=[[INF]*N for _ in range(N)]
    for _ in range(M):
        a,b,c=map(int1,input().split())
        c+=1
        d[a][b]=c
        d[b][a]=c
    d2=[d[i][:] for i in range(N)]
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d2[i][j]=min(d2[i][j],d2[i][k]+d2[k][j])
    ans=0
    for i in range(N):
        for j in range(N):
            if d[i][j]!=INF and d[i][j]!=d2[i][j]:
                ans+=1
    print(ans//2)

if __name__ == '__main__':
    main()

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):
    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda : float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]
    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

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

g = Graph()
for i in range(m):
    a, b, c = map(int, input().split())
    g.add_edge(a-1, b-1, c)
    g.add_edge(b-1, a-1, c)

A = []
for i in range(n):
    d = Dijkstra(g, i)
    for j in range(i+1, n):
        p = d.shortest_path(j)
        for k in range(len(p) - 1):
            A.append("{0},{1}".format(p[k], p[k+1]))
            A.append("{0},{1}".format(p[k+1], p[k]))

print((m*2 - len(set(A)))//2)

Solution (Python):
import sys
N, M = map(int, sys.stdin.readline().strip().split())
 
def warshall_floyd(d):
    
    for k in range(size_v):
        for i in range(size_v):
            for j in range(size_v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
 
edges = []
for i in range(M):
    a, b, c = map(int, sys.stdin.readline().strip().split())
    edges.append((a, b, c))

 
size_v = N + 1
dist=[[float("inf")] * size_v for i in range(size_v)] 
 
for a, b, c in edges:
    dist[a][b] = c
    dist[b][a] = c
for i in range(size_v):
    dist[i][i] = 0
 
dist = warshall_floyd(dist)

  
answer_set = set()
for a, b, c in edges:
    if dist[a][b] == c:
        answer_set.add((a, b, c))
    
print(M - len(answer_set))