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
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
    pars = [set() for _ in range(n)]
    while hq:
        d, x, z = heappop(hq)
        if dist[x] != INF:
            if d == dist[x]:
                pars[x].add(z)
                used_edges[x] |= used_edges[z]
                if z < x:
                    used_edges[x].add((z, x))
                else:
                    used_edges[x].add((x, z))
            continue   
        
        dist[x] = d
        if x != v:
            used_edges[x] |= used_edges[z]
            pars[x].add(z)
            if z < x:
                used_edges[x].add((z, x))
            else:
                used_edges[x].add((x, z))

        for (y, c) in graph[x]:
            if y in pars[x] or pars[y]:
                continue
            heappush(hq, (d+c, y, x))

    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)

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

cost = [[] for _ in range(n)]
edges = dict()
for i in range(m):
    a = abc[i][0] - 1
    b = abc[i][1] - 1
    c = abc[i][2]
    cost[a].append((b, c))
    cost[b].append((a, c))

    edges[str(a) + ' ' + str(b)] = i
    edges[str(b) + ' ' + str(a)] = i

s = set()


from heapq import heappop, heappush
for start in range(n):
    d = [float('inf') for i in range(n)] 
    d[start] = 0

    q = [] 
    prev = [None] * n 
    heappush(q, (d[start], start))
    while q:
        
        du, u = heappop(q) 
        if d[u] < du:
            continue
        for v, weight in cost[u]:
            alt = du + weight
            if d[v] > alt:
                d[v] = alt
                prev[v] = u
                heappush(q, (alt, v))

    

    for goal in range(start + 1, n):
        goal = [goal]
        while prev[goal[-1]] != None:
            goal.append(prev[goal[-1]])
        goal = goal[::-1]

        for j in range(len(goal) - 1):
            edge_idx = edges[str(goal[j]) + ' ' + str(goal[j + 1])]
            s.add(edge_idx)

print(m - len(s))

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



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

N,M = II()
a,b,c = Line(M,3)

E = [[10**30]*N for _ in range(N)]
for i in range(N):
    E[i][i] = 0         
for i in range(M):
    E[a[i]-1][b[i]-1] = c[i]
    E[b[i]-1][a[i]-1] = c[i]     

E2 = WF(E,N)

ans = 0
for i in range(M):
    if E2[a[i]-1][b[i]-1]<c[i]:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
edges = []
G = [[10**8]*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
    edges.append((A-1, B-1, C))

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

ans = 0
for A, B, C in edges:
    flg = False
    for i in range(N):
        for j in range(N):
            if G[i][A]+C+G[B][j] == G[i][j]:
                flg = True
    if flg is False:
        ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
Glaph=[[0 for i in range(N)] for j in range(N)]
flag_ans=[[0 for i in range(N)] for j in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  Glaph[a-1][b-1]=c
  Glaph[b-1][a-1]=c
  
def djikstra(s):
  flag=[0 for i in range(N)]
  cost=[float("Inf") for i in range(N)]
  rout=[-1 for i in range(N)]
  
  cost[s]=0
  flag[s]=1
  
  for i in range(N):  
    minc=float("Inf")
    for j in range(N):
      if  flag[j]==0:
        if Glaph[s][j]!=0:
          if cost[j]>cost[s]+Glaph[s][j]:
            cost[j]=cost[s]+Glaph[s][j]
            rout[j]=s
            if minc>cost[j]:
              k=j
              minc=cost[j]
          elif minc>cost[j]:
            k=j
            minc=cost[j]
        elif minc>cost[j]:
          k=j
          minc=cost[j]

    s=k
    flag[s]=1
  
    flag_ans[ rout[s] ][ s ]=1
    flag_ans[s][ rout[s] ]=1

for i in range(N):
  djikstra(i)
  
ans=0
for i in range(N):
  for j in range(i+1,N):
    if flag_ans[i][j]==0 and Glaph[i][j]!=0:
      ans+=1
print(ans)

Solution (Python):
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
read = sys.stdin.read

N, M, *abc = map(int, read().split())
a, b, c = zip(*zip(*[iter(abc)] * 3))

graph = csr_matrix((c, (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False).astype(int)

answer = 0

for i, j, k in zip(a, b, c):
    if k != distance[i][j]:
        answer += 1

print(answer)

Solution (Python):
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
read = sys.stdin.read

N, M, *abc = map(int, read().split())
a, b, c = zip(*zip(*[iter(abc)] * 3))

graph = csr_matrix((c, (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False)

answer = 0

for i, j, k in zip(a, b, c):
    k = float(k)
    if k != distance[i][j]:
        answer += 1

print(answer)

Solution (Python):
import sys
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
read = sys.stdin.read

N, M, *abc = map(int, read().split())
a, b, c = zip(*zip(*[iter(abc)] * 3))

graph = csr_matrix((c, (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False)

answer = 0

for i, j, k in zip(a, b, c):
    k = float(k)
    if k == distance[i][j]:
        continue

    for s in range(1, N + 1):
        if i == s or j == s:
            continue

        if k + distance[j][s] == distance[i][s]:
            break

        if k + distance[i][s] == distance[j][s]:
            break

    else:
        answer += 1

print(answer)

Solution (Python):

def dijkstra(graph,weight,s,N):
    distance=[1e10 for i in range(N)]
    distance[s]=0
    unvisited=[i for i in range(N)]
    while len(unvisited)>0:
        unvisited.sort(key=lambda x:distance[x])
        v=unvisited.pop(0)
        for w in graph[v]:
            if distance[w]>distance[v]+weight[(v,w)]:
                distance[w] = distance[v] + weight[(v, w)]
    return distance

def e_check(e,d_list,weight,N):
    for i in range(N):
        for j in range(N):
            if e[0]!=i and e[1]!=j and d_list[e[0]][i]+weight[(i,j)]==d_list[j][e[1]]:
                return True
    return False

def e_check_2(E,d_list,weight):
    count=0
    for e in E:
        if d_list[e[0]][e[1]]!=weight[e]:
            count+=1
    return count


if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    graph={i:[] for i in range(N)}
    weight={(i,j):1e10 for i in range(N) for j in range(N)}
    E=[]

    for i in range(M):
        a,b,c = list(map(int, input().split()))
        E.append((a-1,b-1))
        E.append((b-1,a-1))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        weight[(a-1,b-1)]=c
        weight[(b-1,a-1)]=c
    d_list={i:dijkstra(graph,weight,i,N) for i in range(N)}

    ans=e_check_2(E,d_list,weight)

    print(ans//2)

Solution (Python):
N, M = map(int, input().split())
D = [[0 if i == j else 1<<100 for j in range(N)] for i in range(N)]
X = []
for _ 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

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

print(sum([1 if D[a][b] < c else 0 for a, b, c in X]))

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])

def warshall_floyd(): 
    n,w = inpm() 
    d = [[10**10 for i in range(n)] for i in range(n)] 
    
    xyz=[]
    for i in range(w):
        x,y,z = inpm()
        x -= 1
        y -= 1
        xyz.append((x,y,z))
        d[x][y] = z
        d[y][x] = 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])
    return n,w,d,xyz

def main():
    n,w,d,edge=warshall_floyd()
    cnt=0
    for i in range(w):
        flag = False
        x=edge[i][0]
        y=edge[i][1]
        z=edge[i][2]
        for j in range(n):
            if d[j][x] + z == d[j][y]:
                flag = True
                break
            if d[j][y] + z == d[j][x]:
                flag = True
                break
        if not flag:
            cnt+=1
    print(cnt)





if __name__ == "__main__":
    main()

Solution (Python):

import heapq

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

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

INF = float("inf")

dp = [[INF for _ in range(N)] for _ in range(N)]


for i in range(N):
    
    dp[i][i] = 0
    q = []
    
    heapq.heappush(q,(0,i))
    while q:
        
        c,a = heapq.heappop(q)
        
        if dp[i][a] < c:
            continue
        
        for nc,b in es[a]:
            
            if dp[i][b] > dp[i][a] + nc:
                dp[i][b] = dp[i][a] + nc
                
                heapq.heappush(q, (dp[i][b],b))


        

ans = 0
for a in range(N):
    for c,b in es[a]:
        if dp[a][b] != c:
            ans += 1

print(ans//2)

Solution (Python):
import sys
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
new_graph = csgraph_from_dense(graph)
res = floyd_warshall(new_graph)
cnt = 0
for i in range(n):
    for j in range(i, n):
        if graph[i][j] > 0 and graph[i][j] != res[i][j]:
            cnt += 1
print(cnt)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else inf,i) for i in range(n)]
    prev=[0]*n
    q=[i for i in d]
    heapify(q)
    
    
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur][0]+dist
            if alt<d[dst][0]:
                d[dst]=(alt,dst)
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev
    
show_flg=False
show_flg=True

ans=0
n,m=LI()
g,ip=GI(n,m)
mins=[]
for i in range(n):
    d,p=dijkstra(g,i)
    mins.append([i for i,j in d])

for a,b,c in ip:
    k=1
    for y in range(n):
        if y==b:
            continue
        if mins[y][a]+c==mins[y][b]:
            k=0
    ans+=k

print(ans)

Solution (Python):
N, M = map(int, input().split())
INF = 10 ** 7
A = list()
B = list()
C = list()
d = [[INF] * N for i in range(N)]
for m in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)
    C.append(c)
    d[a][b] = c
    d[b][a] = c
for k in range(N):
    d[k][k] = 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 = 0
for m in range(M):
    if d[A[m]][B[m]] < C[m]:
        ans += 1

print(ans)

Solution (Python):
N,M = map(int, input().split())
INF = 10**6
Edge = [[INF]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int, input().split())
    Edge[a-1][b-1] = c
    Edge[b-1][a-1] = c
    
dp = [[INF]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0
        else:
            dp[i][j] = Edge[i][j]
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if Edge[i][j] == INF:
            continue
        if Edge[i][j] > dp[i][j]:
            ans += 1
            
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for i in range(n):
        A[i][i]=0
    ABC=[None]*m
    for i in range(m):
        a,b,c=map(int,input().split())
        a-=1; b-=1
        A[a][b]=c; A[b][a]=c
        ABC[i]=(a,b,c)

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

    ans=0
    for a,b,c in ABC:
        ans+=all(A[u][v]<A[u][a]+c+A[b][v] for u,v in product(range(n),repeat=2))
    print(ans)
resolve()

Solution (Python):
import heapq

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

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


"""
・ノード数が少ないので、全ノード間の最短距離を求めても間に合う
・ある辺eがいずれかの最短距離に含まれる　→　その辺eが結ぶ２ノードの最短距離はeの距離（それぞれの最短距離を束ねてある２ノードの最短距離を作るから）
"""

INF = float("inf")

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

for i in range(N):
    q = []
    d[i][i] = 0
    heapq.heappush(q, (0, i))
    while q:
        cost, a = heapq.heappop(q)
        if d[i][a] < cost:
            continue
        for c,b in es[a]:
            if d[i][a] + c < d[i][b]:
                d[i][b] = d[i][a] + c
                heapq.heappush(q, (d[i][b], b))




cnt = 0
for i in range(N):
    for c, b in es[i]:
        if d[i][b] != c:
            cnt += 1


print(cnt//2)

Solution (Python):
import heapq

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

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

INF = float("inf")

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

for i in range(N):
    q = []
    d[i][i] = 0
    heapq.heappush(q, (0, i))
    while q:
        cost, a = heapq.heappop(q)
        if d[i][a] < cost:
            continue
        for c,b in es[a]:
            if d[i][a] + c < d[i][b]:
                d[i][b] = d[i][a] + c
                heapq.heappush(q, (d[i][b], b))




cnt = 0
for i in range(N):
    for c, b in es[i]:
        if d[i][b] != c:
            cnt += 1


print(cnt//2)

Solution (Python):
n,m=map(int,input().split())
d=[[10**18]*n for i in range(n)]
e=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c
    e.append([a-1,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])

print(sum(c>d[a][b] for a,b,c in e))

Solution (Python):
def warshall_floyd(d, next_node):
    
    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]
                    next_node[i][j] = next_node[i][k]
 
 
INF = float("inf")
 
n, m = map(int, input().split())
d = [[INF] * n for _ in range(n)]
next_node = [list(range(n)) for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for j in range(m):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    d[a][b] = d[b][a] = c
 
warshall_floyd(d, next_node)
 
used_path = set()
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        used_path.add((i, next_node[i][j]))
        used_path.add((next_node[i][j], i))
 
ans = m - len(used_path) // 2
 
print(ans)

Solution (Python):
def warshal(N, 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

def main():
    N, M = map(int, input().split())
    d = [[float('inf')] * N for _ in range(N)]
    edges = []

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

    warshal(N, d)

    cnt = 0
    for edge in edges:
        if d[edge[0]][edge[1]] != edge[2]:
            cnt += 1

    print(cnt)

    

if __name__ == "__main__":
    main()

Solution (Python):
n,m = map(int,input().split())
d =[[float('inf') for _ in range(n)] for _ in range(n)]
edges = []
for _ in range(m):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    edges.append((a,b,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])
s = set()
for i in range(n):
    for j in range(m):
        if d[i][edges[j][0]-1] + edges[j][2] == d[i][edges[j][1]-1]:
            s.add(j)
print(m-len(s))

Solution (Python):

from collections import defaultdict
from heapq import heappop, heappush


class Graph():

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

    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]


g=Graph()
n,m=map(int,input().split())
from collections import defaultdict
e=defaultdict(int)
for _ in range(m):
    a,b,c=map(int,input().split())
    g.add_edge(a,b,c)
    g.add_edge(b,a,c)
    a,b=min(a,b),max(a,b)
    e[(a,b)]+=1



d=[0]*(n+1)
d[0]=1
for i in range(1,n+1):
    dd=Dijkstra(g,i)
    for j in range(i+1,n+1):
        l=dd.shortest_path(j)
        for k in range(1,len(l)):
            a,b=min(l[k-1:k+1]),max(l[k-1:k+1])
            e[(a,b)]=0
ans=0
for v in e.values():
    ans+=v

print(ans)

Solution (Python):
INF = 10**18

N,M = map(int,input().split())
edge = [list(map(int,input().split())) for _ in range(M)]
graph = [[INF for j in range(N)] for i in range(N)]

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

for e in edge:
    graph[e[0]-1][e[1]-1] = e[2]
    graph[e[1]-1][e[0]-1] = e[2]
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] != INF and graph[k][j] != INF:
                graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j])

ans = 0

for e in edge:
    if graph[e[0]-1][e[1]-1] != e[2]:
        ans += 1
        
print(ans)

Solution (Python):
import heapq
N,M=map(int,input().split())
bri=[[] for _ in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  bri[a-1].append([b,c])
  bri[b-1].append([a,c])

ans=0  
for i in range(N):
  a=i+1
  nseen=list(range(1,N+1))
  dist=[float("inf")]*N
  dist[a-1]=0
  q=[[dist[i],i] for i in range(N)]
  heapq.heapify(q)
  while q:
    d,ind=heapq.heappop(q)
    if d<=dist[ind]:
      for n,c in bri[ind]:
        if dist[n-1]>d+c:
          dist[n-1]=d+c
          heapq.heappush(q,[dist[n-1],n-1])
  for b,c in bri[i]:
    if a<b:
      if dist[b-1]<c:
        ans+=1
        
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

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

graph = [[0]*n for i in range(n)]

for i in range(m) :
    graph[A[i]][B[i]] = C[i]
    graph[B[i]][A[i]] = C[i]

graph = csgraph_from_dense(graph)
dist = dijkstra(graph)

ans = 0
for i in range(m) :
    if dist[A[i]][B[i]] != C[i] :
        ans += 1

print(ans)

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

n,m = map(int,input().split())
edges = [[int(x) for x in input().split()] for i in range(m)]
graph = [[False]*n for i in range(n)]
for a, b, c in edges :
    graph[a-1][b-1] = c

graph = csgraph_from_dense(graph)
dist = dijkstra(graph, directed=False).astype(int)

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

print(ans)

Solution (Python):
import heapq
def dijkstra(n, edge, dist, s):
    min_dist = [float('inf')] * n
    min_dist[s] = 0
    next_v = []
    heapq.heappush(next_v, (0, s))
    path = [-1] * n
    
    while True:
        if len(next_v) == 0: break
        d, v = heapq.heappop(next_v)
        
        for u in edge[v]:
            if min_dist[u] > min_dist[v] + dist[v][u]:
                min_dist[u] = min_dist[v] + dist[v][u]
                heapq.heappush(next_v, (min_dist[u], u))
                path[u] = v
                
    return min_dist, path

n, m = map(int, input().split())
dist = [[float('inf') for _ in range(n)] for _ in range(n)]
edge = [[] for _ in range(n)]

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

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

e = set()
for i in range(n):
    md, path = dijkstra(n, edge, dist, i)
    for i, p in enumerate(path):
        if p == -1: continue
        if i <= p: e.add((i, p))
        else: e.add((p, i))

print(m - len(e))

Solution (Python):
INF = float('inf')

def dijkstra(s,N,M,cost,ans):
  d = [INF] * N
  used = [False] * N
  d[s] = 0
  prvv = [[] for _ in range(N)]
  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):
      if d[j] > d[v]+cost[v][j]:
        d[j] = d[v]+cost[v][j]
        prvv[j] = [v]
      elif d[j] == d[v]+cost[v][j]:
        d[j] = d[v]+cost[v][j]
        prvv[j].append(v)
  
  for i, vs in enumerate(prvv):
    for v in vs:
      ans.add(tuple(sorted([v,i])))

  return prvv

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

cost = [[INF for _ in range(N)] for _ in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c


ans =set([])
for i in range(N):
  dijkstra(i,N,M,cost,ans)
print(M-len(ans))

Solution (Python):

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


n,w = map(int,input().split()) 
d = [[float('inf') for i in range(n+1)] for i in range(n+1)] 

W = []
for i in range(w):
    x,y,z = map(int,input().split())
    W.append((x,y,z))
    d[x][y] = z
    d[y][x] = z
for i in range(n+1):
    d[i][i] = 0 
a = 0
warshall_floyd(d)
for i in range(w):
    x,y,z = W[i][0],W[i][1],W[i][2]
    if d[x][y] < z:
        a += 1
print(a)

Solution (Python):

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

Ad = [[] for _ in range(n)]
for _ in range(m):
    ai,bi,ci = map(int, input().split( ))
    ai -= 1
    bi -= 1
    Ad[ai].append((bi,ci))
    Ad[bi].append((ai,ci))

dp = [[10**10 for i in range(n)] for j in range(n)]
for i in range(n):
    dp[i][i] = 0
    for b,c in Ad[i]:
        dp[i][b] = c

ans = []

for k in range(n):
    for i in range(n):
        for b,c in Ad[i]:
            if dp[i][b]>dp[i][k]+dp[k][b]:
                ans.append((i,b))
                dp[i][b] = dp[i][k]+dp[k][b]
        for j in range(n):
            dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])
ans = set(ans)

print(len(ans)//2)

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())
abc=[list(map(int,input().split())) for i in range(m)]

data=np.zeros((n+1,n+1))
for u in abc:
    a,b,c=u
    data[a,b]=c
    data[b,a]=c
qqq=shortest_path(data,directed=False).astype(int)

ans=0
for u in abc:
    a,b,c=u
    if qqq[a][b]!=c:
        ans+=1
print(ans)

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

data=[[inf]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    data[i][i]=0
lst=[]
for u in range(m):
    a,b,c=map(int,input().split())
    data[a][b]=c
    data[b][a]=c
    lst.append([a,b,c])

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

ans=0
for u in lst:
    a,b,c=u
    if data[a][b]!=c:
        ans+=1

print(ans)

Solution (Python):

import sys
input = sys.stdin.readline


from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
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

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

def examD():
    N, M = LI()
    D = [[float("inf") for i in range(N)] for i in range(N)]
    
    XY = [[0,0]]*M
    for i in range(M):
        x, y, z = map(int, input().split())
        XY[i] = [x-1,y-1]
        D[x - 1][y - 1] = z
        D[y - 1][x - 1] = z
    for i in range(N):
        D[i][i] = 0  
    d = copy.deepcopy(D)

    W = warshall_floyd(N, d)
    cur = int(0)
    for i in range(M):
        if D[XY[i][0]][XY[i][1]]>W[XY[i][0]][XY[i][1]]:
            cur += 1
    print(cur)

import sys
import copy
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()