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


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 read_input():
    n, m = map(int, input().split())

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

    return n, m, edges

def submit():
    n, m, edges = read_input()

    
    d = [[float('inf') for _ in range(n)] for _ in range(n)]

    for edge in edges:
        d[edge[0]][edge[1]] = edge[2]
        d[edge[1]][edge[0]] = edge[2]

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

    d = warshall_floyd(d, n)

    
    edge_inuse = [0 for _ in range(m)]
    for e, edge in enumerate(edges):
        for i in range(n):
            for j in range(n):
                dist1 = d[i][j]
                dist2 = d[i][edge[0]] + edge[2] + d[edge[1]][j]

                if dist1 == dist2:
                    edge_inuse[e] = 1
                    break

            if edge_inuse[e] == 1:
                break

    print(m - sum(edge_inuse))
    return


if __name__ == '__main__':
    submit()

Solution (Python):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

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

D = np.full((N, N), IINF)
for a, b, c in ABC:
    D[a - 1][b - 1] = c
    D[b - 1][a - 1] = c


for via in range(N):
    D = np.minimum(D, sum(np.meshgrid(D[via], D[via], sparse=True)))

ans = 0
for a, b, c in ABC:
    if D[a - 1][b - 1] < c:
        ans += 1
print(ans)

Solution (Python):
import os
import sys

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

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

D = np.zeros((N, N))
for a, b, c in ABC:
    D[a - 1][b - 1] = c

min_dist = dijkstra(csgraph_from_dense(D), directed=False)
print((min_dist < D).sum())

Solution (Python):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

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

D = np.full((N, N), IINF)
for a, b, c in ABC:
    D[a - 1][b - 1] = c
    D[b - 1][a - 1] = c


for via in range(N):
    D = np.minimum(D, sum(np.meshgrid(D[via], D[via])))

ans = 0
for a, b, c in ABC:
    if D[a - 1][b - 1] < c:
        ans += 1
print(ans)

Solution (Python):
from scipy.sparse.csgraph import dijkstra
INF = float('inf')
N,M = map(int,input().split())
g = [[INF]*N for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    g[a-1][b-1] = c
    g[b-1][a-1] = c
d = dijkstra(g)
ans = 0
for i in range(N):
    for j in range(N):
        if g[i][j] != INF and g[i][j] > d[i][j]:
            ans += 1
ans //= 2
print(ans)

Solution (Python):
from collections import defaultdict
from itertools import product, combinations

def floyd_warshall(V, E):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
    Output:
        If there exists a negative cycle, return None
        Otherwise return dist: the table of the minimum cost between arbitrary vertex u, v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = {u: {v: INF for v in V} for u in V}
    path = {u: {v: None for v in V} for u in V}
    for v in V:
        dist[v][v] = 0; path[v][v] = -1
        for u, c in E[v].items(): dist[v][u] = c; path[v][u] = v;
    for k, i, j in product(V, repeat=3):
        if dist[i][j] > dist[i][k] + dist[k][j]:
            dist[i][j] = dist[i][k] + dist[k][j]
            path[i][j] = path[k][j]
    for v in V:
        if dist[v][v] < 0: return None, None
    return dist, path


N, M = map(int, input().split())
E = defaultdict(dict)
cand = set()
for _ in range(M):
    a, b, c = map(int, input().split())
    E[a-1][b-1] = c
    E[b-1][a-1] = c
    cand |= {(min(a-1, b-1), max(a-1, b-1))}
V = list(range(N))
_, path = floyd_warshall(V, E)
for i, j in combinations(V, 2):
    temp = set()
    while path[i][j] != -1:
        temp |= {(path[i][j], j)} if path[i][j] < j else {(j, path[i][j])}
        j = path[i][j]
    cand -= temp
print(len(cand))

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

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

edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0] * N for _ in range(N)]
for a,b,c in edge:
  graph[a-1][b-1] = c
  
graph = csgraph_from_dense(graph)

dist = floyd_warshall(graph,directed=False)
answer = (graph > dist).sum()
print(answer)

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

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

edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0] * N for _ in range(N)]
for a,b,c in edge:
  graph[a-1][b-1] = c
  
graph = csgraph_from_dense(graph)

dist = floyd_warshall(graph,directed=False,overwrite=True).astype(int)

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

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

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

edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0] * N for _ in range(N)]
for a,b,c in edge:
  graph[a-1][b-1] = c
  
graph = csgraph_from_dense(graph)

dist = floyd_warshall(graph,directed=False).astype(int)

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

Solution (Python):
from itertools import permutations
from scipy.sparse.csgraph import floyd_warshall
n,m=map(int,input().split())
table=[[0]*n for i in range(n)]
Edge=[None]*m
for i in range(m):
    a,b,c=map(int,input().split())
    table[a-1][b-1]=c
    table[b-1][a-1]=c
    Edge[i]=[a,b,c]
d=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)
ans=0
for i in range(m):
  a,b,c=Edge[i]
  if d[a-1][b-1]<c:
    ans+=1
print(ans)

Solution (Python):











import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = [[] for _ in range(N)]
    used_edge = set()

    
    def dijkstra(start, edge):
        costs=[inf]*N
        costs[start]=0
        queue = [(0, start, (-1,-1))]  
        hash = {}
        while queue:
            c, from_, e = heappop(queue)
            hash[from_]=1
            if costs[from_] >= c:
                costs[from_] = c
                used_edge.add(e)
            for cost,node in edge[from_]:
                if node in hash:
                    continue
                e = tuple(sorted([from_,node]))
                heappush(queue, (c + cost, node,e))



    for _ in range(M):
        a, b, c = MI_()
        c += 1
        edge[a].append((c, b))
        edge[b].append((c, a))
        
    for start in range(N):
        dijkstra(start, edge)
    
    num_used_edge = len(used_edge)-1
    print(M-num_used_edge)
    
if __name__ == '__main__':
    main()

Solution (Python):

import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())



from collections import defaultdict
import heapq












def dijkstra(s: int, n: int, graph: dict) -> list:
  INF = 10 ** 10 
  que = []    
  routelist = [-1] * n 
  heapq.heappush(que, (0, s))
  min_dist_list = [INF] * n
  min_dist_list[s] = 0
  while que:
    now_dist, node = heapq.heappop(que)

    if min_dist_list[node] < now_dist:
      continue

    for to, dist in graph[node]:
      new_dist = now_dist + dist
      if min_dist_list[to] > new_dist:
        min_dist_list[to] = new_dist
        routelist[to] = node
        heapq.heappush(que, (new_dist, to))

  return min_dist_list, routelist

N, M = mi()
SGDs = [tuple(mi()) for _ in range(M)] 


Graph = defaultdict(list) 
for s, g, d in SGDs: 
  s, g = s-1, g-1 
  Graph[s].append((g, d)) 
  Graph[g].append((s, d)) 



Contained_Edge = set()
for eachstart in range(N): 
  routelist = dijkstra(eachstart, N, Graph)[1] 
  for i, prev in enumerate(routelist):
    
    if prev+1: 
      Contained_Edge.add((i,prev))
      Contained_Edge.add((prev,i))


All_Edges = {(s-1,g-1) for s, g, d in SGDs}




print(len(All_Edges - Contained_Edge))

Solution (Python):
class WarshallFloyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float("inf") for i in range(N)]for i in range(N)] 
        self.next = [[ j for j in range(N)]for i in range(N)]  
        self.e = {}
        for i in range(N):
            self.e[i] = []

    def add(self, u, v, c, directed=False):
        """
        0-indexedであることに注意
        u = from, v = to, c = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def printPath(self,start,goal):
        cur = start
        l = []
        while cur != goal:
            t = self.next[cur][goal]
            self.e[cur].append(t)
            
            cur = t
        return l

    def dumpPath(self):
        for i in range(self.N):
            for j in range(self.N):
                if i != j:
                    self.printPath(i,j)

    def WarshallFloyd_search(self):
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    if self.d[i][j] > self.d[i][k] + self.d[k][j]:
                        self.d[i][j] = self.d[i][k] + self.d[k][j]
                        self.next[i][j] = self.next[i][k]


        self.dumpPath() 
        for i in range(self.N):
            self.d[i][i] = 0
        return self.e
        return self.d


N,M = map(int,input().split())
W = WarshallFloyd(N)
for i in range(M):
    a,b,c = map(int,input().split())
    W.add(a-1,b-1,c)

l = W.WarshallFloyd_search()
ans = M*2
for i in range(N):
    ans -= len(set(l[i]))
print(ans//2)

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

l=[list(map(int,input().split())) for i in range(M)]
inf=10**20
a=[[inf]*N for i in range(N)]
e=[[0]*N for i in range(N)]
for i,j,k in l:
    a[i-1][j-1]=k
    a[j-1][i-1]=k
    e[i-1][j-1]=1
    e[j-1][i-1]=1

ans=0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if a[i][j]>a[i][k]+a[k][j]:
                if e[i][j]==1:
                    ans+=1
                    e[i][j]=e[j][i]=0
                a[i][j]=a[i][k]+a[k][j]

print(ans)

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
distance=[[99999999 for i in range(n)] for i in range(n)]
for i in range(n):
  distance[i][i]=0
for i in range(m):
  distance[l[i][0]-1][l[i][1]-1]=l[i][2]
  distance[l[i][1]-1][l[i][0]-1]=l[i][2]

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

ct=m
for k in range(m):
  for i in range(n):
    for j in range(n):
      if i!=j:
        if distance[i][j]==distance[i][l[k][0]-1]+l[k][2]+distance[l[k][1]-1][j]:
          ct-=1
          break
    else:
      continue
    break
print(ct)

Solution (Python):
N,M=map(int, input().split())
edge=[list(map(int,input().split())) for i in range(M)]
inf=10**20
c=[[inf]*N for i in range(N)]
e=[[0]*N for i in range(N)]
for i,j,w in edge:
    c[i-1][j-1]=w
    c[j-1][i-1]=w
    e[i-1][j-1]=1
    e[j-1][i-1]=1
for i in range(N):
    c[i][i]=0
ans=0
def wf(c,N):
    global ans
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if c[i][j]>c[i][k]+c[k][j]:
                    if e[i][j]==1:
                        ans+=1
                        e[i][j]=e[j][i]=0
                    c[i][j]=c[i][k]+c[k][j]
wf(c,N)
print(ans)

Solution (Python):
import heapq
N,M=map(int,input().split())
R=[]
G=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    G[a].append((b,c))
    G[b].append((a,c))
    R.append((a,b,c))
Q=[[0]*N for i in range(N)]
INF=10**9
for i in range(N):
    stack=[]
    g=[INF for i in range(N)]
    g[i]=0
    n=1
    for b,c in G[i]:
        heapq.heappush(stack,(g[i]+c,i,b))
    used=[[0]*N for i in range(N)]
    while(stack):
        if n==N:
            break
        c,a,b=heapq.heappop(stack)
        g[b]=min(g[b],c)

        used[a][b]=1
        used[b][a]=1
        for j in G[b]:
            if used[b][j[0]] or g[j[0]]!=INF:
                continue
            if g[j[0]]<=g[b]+j[1]:
                continue
            heapq.heappush(stack,(g[b]+j[1],b,j[0]))
    for j in range(i+1,N):
        Q[i][j]=g[j]
ans=0
for a,b,c in R:
    if b<a:
        a,b=b,a
    if Q[a][b]<c:
        ans+=1
print(ans)

Solution (Python):
import heapq
N,M=map(int,input().split())
R=[]
G=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    G[a].append((b,c))
    G[b].append((a,c))
    R.append((a,b,c))
Q=[[0]*N for i in range(N)]
INF=10**9
for i in range(N):
    stack=[]
    g=[INF for i in range(N)]
    g[i]=0
    n=1
    for b,c in G[i]:
        heapq.heappush(stack,(g[i]+c,i,b))
    used=[[0]*N for i in range(N)]
    while(stack):
        if n==N:
            break
        c,a,b=heapq.heappop(stack)
        g[b]=min(g[b],c)

        used[a][b]=1
        used[b][a]=1
        for j in G[b]:
            if used[b][j[0]] or g[j[0]]!=INF:
                continue
            if g[j[0]]<=g[b]+j[1]:
                continue
            heapq.heappush(stack,(g[b]+j[1],b,j[0]))
    for j in range(i+1,N):
        Q[i][j]=g[j]
ans=0
for a,b,c in R:
    if b<a:
        a,b=b,a
    if Q[a][b]<c:
        ans+=1
print(ans)

Solution (Python):
import heapq
N,M=map(int,input().split())
R=[]
G=[[] for i in range(N)]
for i in range(M):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    G[a].append((b,c))
    G[b].append((a,c))
    R.append((a,b,c))
Q=[[0]*N for i in range(N)]
INF=10**9
for i in range(N):
    stack=[]
    g=[INF for i in range(N)]
    g[i]=0
    n=1
    for b,c in G[i]:
        heapq.heappush(stack,(g[i]+c,i,b))
    used=[[0]*N for i in range(N)]
    while(stack):
        if n==N:
            break
        c,a,b=heapq.heappop(stack)
        g[b]=min(g[b],c)
        used[a][b]=1
        used[b][a]=1
        for j in G[b]:
            if used[b][j[0]] or g[j[0]]!=INF:
                continue
            heapq.heappush(stack,(g[b]+j[1],b,j[0]))
    for j in range(i+1,N):
        Q[i][j]=g[j]
ans=0
for a,b,c in R:
    if b<a:
        a,b=b,a
    if Q[a][b]<c:
        ans+=1
print(ans)

Solution (Python):


N,M=map(int,raw_input().split())
D=[[1145141919]*101 for _ in range(101)]
R=[[1145141919]*101 for _ in range(101)]

A=set()
for i in range(M):
    a,b,c=map(int,raw_input().split())
    D[a][b]=c;D[b][a]=c
    R[a][b]=c;R[b][a]=c
    A.add((min(a,b),max(a,b)))

for i in range(1,N+1):D[i][i]=0


for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if D[i][j]>D[i][k]+D[k][j]:
                D[i][j]=D[i][k]+D[k][j]    
ans=0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if R[i][j]==1145141919:continue
        if D[i][j]!=R[i][j]:ans+=1
print(ans)

Solution (Python):
from collections import defaultdict

class dijkstra(object):
    def __init__(self, start, n, E, INF=1e10):
        self.INF = INF
        self.start = start
        self.n = n
        self.V = [0 for _ in range(n + 1)]
        self.E = E
        self.d = [INF for _ in range(n + 1)]
        self.d[start] = 0

    def run(self):
        Q = [[i, self.d[i]] for i in range(1, self.n + 1)]

        while(len(Q) > 0):
            Q.sort(key=lambda x: x[1], reverse=True)
            u = Q.pop()[0]
            for v, l in self.E[u].items():
                if self.d[v] > self.d[u] + l[0]:
                    self.d[v] = self.d[u] + l[0]
                    self.V[v] = u
            Q = [[x[0], self.d[x[0]]] for x in Q]

    def count_path(self):
        def find_path(i, Qv):
            Qv[i] += 1
            if i != self.start:
                self.E[i][self.V[i]][-1] += 1
                self.E[self.V[i]][i][-1] += 1
                Qv = find_path(self.V[i], Qv)
            return Qv

        Qv = [0 for _ in range(self.n + 1)]
        for i in range(1, self.n + 1):
            if i == self.start or Qv[i] > 0:
                continue
            Qv = find_path(i, Qv)

        return self.E

n, m = map(int, input().split())
E_list = [list(map(int, input().split())) for _ in range(m)]
E = defaultdict(dict)
for j in range(m):
    a, b, c = E_list[j]
    E[a][b] = [c, 0]
    E[b][a] = [c, 0]
for i in range(1, n + 1):
    D = dijkstra(i, n, E)
    D.run()
    E = D.count_path()
ans = 0
for v in E.values():
    for v2 in v.values():
        if v2[-1] == 0:
            ans += 1
print(ans // 2)

Solution (Python):
n,m=map(int,input().split())
d=[[float('inf') for i in range(n)] for i in range(n)]
r=[list(map(int,input().split())) for i in range(m)]

from scipy.sparse.csgraph import floyd_warshall

for u,v,c in r:
    u,v=u-1,v-1
    d[u][v]=d[v][u]=c

d=floyd_warshall(d).tolist()

cnt=0
for u,v,c in r:
    u,v=u-1,v-1
    if d[u][v]!=c:
        cnt+=1
print(cnt)

Solution (Python):
n,m=map(int,input().split())
d=[[float('inf') for i in range(n)] for i in range(n)]
r=[list(map(int,input().split())) for i in range(m)]

def wf(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


for u,v,c in r:
    u,v=u-1,v-1
    d[u][v]=d[v][u]=c

wf(d)

cnt=0
for u,v,c in r:
    u,v=u-1,v-1
    if d[u][v]!=c:
        cnt+=1
print(cnt)

Solution (Python):
n,m=map(int,input().split())
d=[[float('inf') for i in range(n)] for i in range(n)]
r=[list(map(int,input().split())) for i in range(m)]

def wf(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


for u,v,c in r:
    u,v=u-1,v-1
    d[u][v]=d[v][u]=c

wf(d)

cnt=0
for u,v,c in r:
    u,v=u-1,v-1
    if d[u][v]!=c:
        cnt+=1
print(cnt)

Solution (Python):
N,M=list(map(int,input().split()))
e_list = [[] for i in range(N)]
e_list2 = []
for i in range(M):
    a,b,d = list(map(int,input().split()))
    a=a-1
    b=b-1
    e_list[a].append([b,d])
    e_list[b].append([a,d])
    e_list2.append([a,b,d])

dist_list = []
import heapq
for i in range(N):
    vi = i
    min_d_list = [10**27 for i in range(N)]
    min_d_list[vi] = 0
    prev_list = [-1 for i in range(N)]
    q = []
    for i in range(N):
        heapq.heappush(q,[min_d_list[i],i])

    while len(q)>0:
        d,v = heapq.heappop(q)
        for e in e_list[v]:
            v1,d1=e
            if min_d_list[v1]>d+d1:
                min_d_list[v1]=d+d1
                prev_list[v1]=v
                heapq.heappush(q,[d+d1,v1])
    dist_list.append(min_d_list)
count=len(e_list2)
for e in e_list2:
    for i in range(N):
        if dist_list[i][e[0]]+e[2]==dist_list[i][e[1]]:
            count-=1
            break

print(count)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) 


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

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

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

min_Graph = copy.deepcopy(Graph)
used = [[0 for i in range(N)] for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            min_Graph[i][j] = min(min_Graph[i][j],min_Graph[i][k]+min_Graph[k][j])

ans = 0
for i in range(M):
    a,b,c = routes[i]
    if min_Graph[a][b] == c:
        pass
    else:
        ans += 1

print(ans)

Solution (Python):

N,M=map(int,input().split())
inf=10**9

class Node():
	def __init__(self, ix):
		self.ix = ix 
		self.done = False 
		self.pay = {} 
		self.paid = -1 
		self.prev = -1 
	def __str__(self):
		
		return '{} <- [{}] <- {}, done:{}, pay:{}'.format(self.ix, self.paid, self.prev, self.done, self.pay)


nodes = []
for i in range(N):
	nodes.append(Node(i))



edges = []
for _ in range(N):
	edges.append([0]*N)




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

for i in range(N):
	nodes[i].prev = i 
	nodes[i].paid = 0 
	nodes[i].done = True 
	n_done = 1 
	while n_done < N: 
		to_conf_ix = -1 
		to_conf_paid = 10**9 
		for node in nodes:
			
			if node.done:
				
				for child in list(node.pay.keys()):
					
					if not nodes[child].done:
						
						
						newcost = node.paid + node.pay[child]
						
						flag = (nodes[child].paid < 0) or (newcost < nodes[child].paid)
						
						
						if flag:
							nodes[child].paid = newcost
							nodes[child].prev = node.ix
						if newcost < to_conf_paid:
							to_conf_paid = newcost
							to_conf_ix = child
		
		nodes[to_conf_ix].done = True
		
		n_done += 1
		
	
	for j in range(N):
		k = nodes[j].prev
		edges[j][k], edges[k][j] = 0, 0

	
	for j in range(N):
		nodes[j].paid, nodes[j].prev = -1, -1
		nodes[j].done = False



ans = 0
for i in range(N):
	ans += sum(edges[i])
print(ans//2)

Solution (Python):

N,M=map(int,input().split())
inf=10**9

class Node():
	def __init__(self, ix):
		self.ix = ix 
		self.done = False 
		self.pay = {} 
		self.paid = -1 
		self.prev = -1 
	def __str__(self):
		
		return '{} <- [{}] <- {}, done:{}, pay:{}'.format(self.ix, self.paid, self.prev, self.done, self.pay)


nodes = []
for i in range(N):
	nodes.append(Node(i))



edges = []
for _ in range(N):
	edges.append([0]*N)




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

for i in range(N):
	
	
	nodes[i].prev = i 
	nodes[i].paid = 0 
	nodes[i].done = True 
	n_done = 1 
	while n_done < N: 
		to_conf_ix = -1 
		to_conf_paid = 10**9 
		for node in nodes:
			
			if node.done:
				
				
				
				for child in list(node.pay.keys()):
					
					if not nodes[child].done:
						
						
						newcost = node.paid + node.pay[child]
						
						flag = (nodes[child].paid < 0) or (newcost < nodes[child].paid)
						
						
						
						
						if flag:
							nodes[child].paid = newcost
							nodes[child].prev = node.ix
						if newcost < to_conf_paid:
							to_conf_paid = newcost
							to_conf_ix = child
						
						
		
		nodes[to_conf_ix].done = True
		
		n_done += 1
		
		
		
		
		
		
	
	for j in range(N):
		k = nodes[j].prev
		edges[j][k], edges[k][j] = 0, 0

	
	for j in range(N):
		nodes[j].paid, nodes[j].prev = -1, -1
		nodes[j].done = False



ans = 0
for i in range(N):
	ans += sum(edges[i])
print(ans//2)

Solution (Python):
n,m = map(int, input().split())
INF = 1000*n+1

edge = [[INF for _ in range(n)] for _ in range(n)]
d = [[INF for _ in range(n)] for _ in range(n)]

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

def dijkstra(i):
    
    d[i][i] = 0
    used = [False] * n

    while True:
        v = -1
        for j in range(n):
            if used[j] == False and (v == -1 or d[i][j] < d[i][v]):
                v = j
        if v == -1:
            break
        used[v] = True
        for k in range(n):

            d[i][k] = min(d[i][k], d[i][v] + edge[v][k])
            d[k][i] = d[i][k]


for i in range(n):
    dijkstra(i)


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

print(ans)

Solution (Python):
N,M=map(int,input().split())
from collections import defaultdict
B=[tuple(map(int,input().split())) for i in range(M)]
dist=defaultdict(lambda : float('inf'))
for i,x in enumerate(B):
    a,b,c=x[0]-1,x[1]-1,x[2]
    dist[(a,b)]=c
    dist[(b,a)]=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[(j,k)])
            dist[(j,i)]=dist[(i,j)]
cnt=0
for x in B:
    a,b,c=x[0]-1,x[1]-1,x[2]
    if dist[(a,b)]!=c:
        cnt+=1
print(cnt)

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

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

edge = [[int(x) for x in input().split()] for _ in range(M)]

graph = np.zeros((N,N)) 
for a,b,c in edge:
  graph[a-1,b-1] = c

dist = shortest_path(graph,directed=False).astype(int)

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

Solution (Python):
import copy

def warshall_floyd(V, E):
    INF = 10 ** 9
    d = [[[INF, 0] for j in range(V + 1)] for i in range(V + 1)]
    for i, j, c in E:
        d[i][j] = [c, 0]
        d[j][i] = [c, 0]
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i][k][0] + d[k][j][0]
                if d[i][j][0] > dk:
                    d[i][j] = [dk, k]
                    d[j][i] = [dk, k]
    return d

def find_path(i, j, d, E):
    k = d[i][j][1]
    if k == 0:
        E[i][j] += 1
        E[j][i] += 1
        return E
    E = find_path(i, k, d, E)
    E = find_path(k, j, d, E)
    return E

n, m = map(int, input().split())
E = [[None for j in range(n + 1)] for i in range(n + 1)]
E_list = []
for i in range(m):
    a, b, c = map(int, input().split())
    E_list.append([a, b, c])
    E[a][b] = 0
    E[b][a] = 0
d = warshall_floyd(n, E_list)
ans = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        E = find_path(i, j, d, E)
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if E[i][j] == 0:
            ans += 1
print(ans)

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n,m = map(int,input().split())
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())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
edge = deepcopy(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])
ans = set()
for i in range(n):
    for j in range(n):
        if edge[i][j] < inf and edge[i][j] > 0:
            ans.add((i,j))
for i in range(n):
    a = set()
    for j in range(n):
        if edge[i][j] !=inf and edge[i][j] > d[i][j]:
            a.add((i,j))
    ans = ans & (ans-a)
print(m-len(ans)//2)

Solution (Python):
N, M = map(int, input().split())
INF = 10 ** 9
dist = [[INF]*N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

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

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

ans = 0

for i in range(M):
    a, b, c = mem[i]
    if c != dist[a][b]:
        ans += 1

print(ans)

Solution (Python):
from heapq import heappush, heappop
from functools import reduce
from operator import or_


N, M = map(int, input().split())
a, b, c = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)


G = [{} for _ in range(N + 1)]
for x, y, w in zip(a, b, c):
    G[x][y] = w
    G[y][x] = w

INF = 10**10


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    res = set()
    heappush(q, (0, s, s))
    while q:
        c, i, p = heappop(q)
        if c < dp[i]:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j, i))
        if c == dp[i] and i != p:
            res.add((p, i))
    return res



ans = M - len(reduce(or_, (dijkstra(G, i) for i in range(1, N + 1)))) // 2


print(ans)