Problem:
 Score : 400 points    Problem Statement You are given an undirected connected weighted graph with N vertices and M edges that contains neither self-loops nor double edges. The i -th (1≤i≤M) edge connects vertex a_i and vertex b_i with a distance of c_i . Here, a self-loop is an edge where a_i = b_i (1≤i≤M) , and double edges are two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M) . A connected graph is a graph where there is a path between every pair of different vertices. Find the number of the edges that are not contained in any shortest path between any pair of different vertices.      Constraints  2≤N≤100   N-1≤M≤min(N(N-1)/2,1000)   1≤a_i,b_i≤N   1≤c_i≤1000  c_i is an integer.  The given graph contains neither self-loops nor double edges.  The given graph is connected.         Input The input is given from Standard Input in the following format:  N  M  a_1  b_1  c_1  a_2  b_2  c_2  :  a_M  b_M  c_M       Output Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.        Sample Input 1 3 3
1 2 1
1 3 1
2 3 3      Sample Output 1 1  In the given graph, the shortest paths between all pairs of different vertices are as follows:   The shortest path from vertex 1 to vertex 2 is: vertex 1 → vertex 2 , with the length of 1 .  The shortest path from vertex 1 to vertex 3 is: vertex 1 → vertex 3 , with the length of 1 .  The shortest path from vertex 2 to vertex 1 is: vertex 2 → vertex 1 , with the length of 1 .  The shortest path from vertex 2 to vertex 3 is: vertex 2 → vertex 1 → vertex 3 , with the length of 2 .  The shortest path from vertex 3 to vertex 1 is: vertex 3 → vertex 1 , with the length of 1 .  The shortest path from vertex 3 to vertex 2 is: vertex 3 → vertex 1 → vertex 2 , with the length of 2 .   Thus, the only edge that is not contained in any shortest path, is the edge of length 3 connecting vertex 2 and vertex 3 , hence the output should be 1 .       Sample Input 2 3 2
1 2 1
2 3 1      Sample Output 2 0  Every edge is contained in some shortest path between some pair of different vertices.

Solution (Python):
import sys


import heapq
def dijkstra_heap(s, n, edges):
    
    dist = [float("inf")] * n
    used = [True] * n 
    dist[s] = 0
    used[s] = False
    used_edges = set()
    edgelist = []
    for (d, e) in edges[s]:
        
        heapq.heappush(edgelist, (d, e, s))
    while edgelist:
        d, e, s = heapq.heappop(edgelist)
        if dist[e] >= d:
            if s < e:
                used_edges.add((s, e))
            else:
                used_edges.add((e, s))

        
        if not used[e]:
            continue
        dist[e] = d
        used[e] = False

        """
        if s < e:
            used_edges.add((s, e))
        else:
            used_edges.add((e, s))
        """
        for (nd, ne) in edges[e]:
            if used[ne]:
                heapq.heappush(edgelist, (nd + dist[e], ne, e))
    return dist, used_edges

N, M = map(int, sys.stdin.readline().strip().split())

edges = [[] for _ in range(N)]
all_edges = set()
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().strip().split())
    edges[a-1].append((c, b-1))
    edges[b-1].append((c, a-1))
    if a < b:
        all_edges.add((a-1, b-1))
    else:
        all_edges.add((b-1, a-1))

for i in range(N):
    min_d, used_edges = dijkstra_heap(i, N, edges)
    
    all_edges -= used_edges

print(len(all_edges))

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

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

for k in range(N):
    dist[k][k] = 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 = 0
for (u, v, cost) in edges:
    flag = False
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            flag |= ((dist[i][u] + cost + dist[v][j]) == dist[i][j])
    ans += 1 - int(flag)
print(ans)

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

import heapq
def dijkstra_heap(s):
  
  dist=[float("inf")]*size_v  
  used=[False]*size_v
  dist[s]=0
  used[s]=True

  hq_edge=[]
  for v,w,i in graph[s]:
    heapq.heappush(hq_edge,(w,v,i))

  while hq_edge:
    min_w,min_v,ei=heapq.heappop(hq_edge)
    if dist[min_v]>=min_w:
      answer_set.add(ei)
    
    if used[min_v]:
      continue

    dist[min_v]=min_w
    used[min_v]=True
    for v,w,ei2 in graph[min_v]:
      if not used[v]:
        heapq.heappush(hq_edge,(min_w+w,v,ei2))

  return dist

graph=[[] for _ in range(N+1)]
for i in range(M):
  a,b,c=map(int,input().split())
  graph[a].append((b,c,i))
  graph[b].append((a,c,i))


size_v=N+1
answer_set=set()
for i in range(1,N+1):
  dist=dijkstra_heap(i)
  
    

print(M-len(answer_set))

Solution (Python):
N,M=map(int,input().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

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


size_v=N+1
dist=[[float("inf")]*size_v for i in range(size_v)] 

for a,b,c in abclist:
  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 abclist:
  if dist[a][b]==c:
    answer_set.add((a,b,c))
    
print(M-len(answer_set))

Solution (Python):






import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


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(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count





N,M = inputIL()


class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for j in range(N)]
    self.prev = [[i for j in range(N)] for i in range(N)]
    for i in range(N):
      self.prev[i][i] = i

  def add(self, u, v, c, directed=False):
    if directed is False:
      self.d[u][v] = c
      self.d[v][u] = c
    else:
      self.d[u][v] = c

  def WarshallFloyd_search(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          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]
            if i!=j:
              self.prev[i][j] = self.prev[k][j]
          
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d

dic = set()  
graph = WarshallFloyd(N)
for _ in range(M):
  u, v, c = inputIL()
  dic.add((u-1,v-1))
  dic.add((v-1,u-1))
  graph.add(u-1,v-1,c)
graph.WarshallFloyd_search()

used = set()
for i in range(N):
  for j in range(i+1,N):
    now = j
    while now != i:
      prev = graph.prev[i][now]
      used.add((now,prev))
      used.add((prev,now))
      now = prev

print(len(dic-used)//2)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, m = map(int, readline().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
abc = [list(map(int, readline().split())) for _ in range(m)]
for a, b, c in abc:
    graph[a][b] = c
    graph[b][a] = c
cost = floyd_warshall(csr_matrix(graph))
cnt = 0
for a, b, c in abc:
    if cost[a][b] < c:
        cnt += 1
print(cnt)

Solution (Python):
import networkx as nx
import itertools

N, M = map(int, input().split())
G = nx.Graph()
G.add_weighted_edges_from([map(int, input().split()) for _ in range(M)])
S = nx.floyd_warshall(G)

ans = M
for i, j, d in G.edges(data=True):
    for s, t in itertools.combinations(G.nodes(), 2):
        if S[s][i] + d['weight'] + S[j][t] == S[s][t]:
            ans -= 1
            break
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections
from heapq import *

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**5
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    root = [[] for _ in range(N)]
    for i in range(M):
        a,b,c = LI()
        root[a-1].append((b-1,c,i))
        root[b-1].append((a-1,c,i))

    rest = [1] * M
    q = []
    heapify(q)

    for i in range(N):
        node = [INF] * N
        heappush(q,(0,i,-1))
        while q:
            d,v,m = heappop(q)
            if node[v] < d: continue
            if m >= 0: rest[m] = 0
            for u,c,n in root[v]:
                if d + c < node[u]:
                    node[u] = d + c
                    heappush(q,(d+c,u,n))
    print(sum(rest))




if __name__ == '__main__':
    main()

Solution (Python):

def dijkstra_back(s,t,n,w,cost):
    
    prev = [s] * n 
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path


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

cost = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(w):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z

check = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(i+1,n):
        tmp = dijkstra_back(i,j,n,w,cost)
        
        for k in range(len(tmp)-1):
            
            check[min(tmp[k],tmp[k+1])][max(tmp[k],tmp[k+1])] = 1





print(w - sum(map(sum, check)))

Solution (Python):
import heapq

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Used = [1] * M
Q = []

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

for i in range(N):
    now = (0, i)
    Seen = [-1] * N
    used = [-1] * N
    wait = []
    heapq.heappush(wait, now)
    Seen[i] = 0
    while len(wait) > 0:
        time, now = heapq.heappop(wait)
        for nex, cost, bridgenum in Edge[now]:
            if Seen[nex] == -1:
                Ne = (time + cost, nex)
                Seen[nex] = time + cost
                heapq.heappush(wait, Ne)
                used[nex] = bridgenum
            elif Seen[nex] > time + cost:
                Ne = (time + cost, nex)
                Seen[nex] = time + cost
                heapq.heappush(wait, Ne)
                used[nex] = bridgenum
    for j in range(N):
        if used[j] != -1:
            Used[used[j]] = 0
print(sum(Used))

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

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


dist = []
for i in range(N):
  tmp = []
  for _ in range(N):
    tmp.append(float('inf'))
  dist.append(tmp)
  dist[i][i] = 0  


a = []
b = []
c = []
for _ in range(M):
  x = list(map(int, input().split()))
  a.append(x[0] - 1)
  b.append(x[1] - 1)
  c.append(x[2])
  dist[a[-1]][b[-1]] = x[2]
  dist[b[-1]][a[-1]] = x[2]


dist = floyd_warshall(dist)
dist = dist.astype(int).tolist()


res = 0
for i in range(M):
  if c[i] > dist[a[i]][b[i]]:
    res += 1
    
print(res)

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

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

edges = []

d = [[float("inf")]*n for _ in range(n)]
for i in range(w):
    x,y,z = map(int, input().split())
    x -= 1
    y -= 1
    d[x][y] = z
    d[y][x] = z
    edges.append((x,y,z))

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


csr = csr_matrix(d)
dp = floyd_warshall(csr)
ans = 0


for i, j, c in edges:
    
    if dp[i,j] < c:
        ans += 1
print(ans)

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

    def __init__(self,n,_first_index=0):
        self.v = n
        self._first_idx=_first_index
        self.d = [[1e100]*(n+_first_index) for _ in range(n+_first_index)]
        for i in range(n+_first_index):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        f=self._first_idx
        for k in range(f,self.v+f):
            for i in range(f,self.v+f):
                for j in range(f,self.v+f):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d
w=WarshallFloyd(n,1)
l=[]
for i in range(m):
    x,y,c=map(int,input().split())
    w.path(x,y,c)
    x,y=sorted([x,y])
    l.append([x,y,c])
d=w.build()
ans=0
for a,s,c in l:
    f=1
    for y in range(1,n+1):
        if d[y][s]==d[y][a]+c:f=0;break
    ans+=f
print(ans)

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

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

row,col,data = zip(*abc)
L = csr_matrix((data, (row,col)), shape=(n+1,n+1))
_,path = dijkstra(L,directed = False, return_predecessors = True)

s,e = np.where(path>0)
path_use = set(map(tuple,np.vstack([path[s,e],e]).T))

print( m - len(path_use)//2)

Solution (Python):
def main():
	n,m=map(int,input().split())
	inf=10**15
	dis=[[inf for _ in range(n)]for _ in range(n)]
	for i in range(n):
		dis[i][i]=0
	node=[]
	for i in range(m):
		a,b,c=map(int,input().split())
		dis[a-1][b-1]=c
		dis[b-1][a-1]=c
		node.append((a-1,b-1,c))
	for i in range(n):
		for j in range(n):
			for k in range(n):
				dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k])
	ans=0
	for x in node:
		f=0
		for i in range(n-1):
			if f:
				break
			for j in range(i+1,n):
				if dis[i][j]==dis[i][x[0]]+x[2]+dis[x[1]][j]:
					f=1
					break
				elif dis[i][j]==dis[i][x[1]]+x[2]+dis[x[0]][j]:
					f=1
					break
		if f==0:
			ans+=1
	print(ans)
if __name__ == '__main__':
	main()

Solution (Python):
'''
ダイクストラ法。
始点を固定した時にすべての頂点に対する最短経路を計算する。
O(|E|log|V|)でベルマンフォードより速いが、
負の辺が含まれる場合は使えない。

'''

import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        d:int
            cost
        directed:bool
            there is direction
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        """
        Parameters
        ----------
        u:int
            from node
        v:int
            to node
        """
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        Parameters
        ----------
        s:int
            始点

        Return
        ----------
        d:dict(int:int)
            shortest cost from start node to each node 
            {to : cost}

        prev:dict(int:int)
            previous node on the shortest path
            {from : to}
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        """
        Parameters
        ----------
        start:int
            start node
        goal:int
            goal node

        Return
        ----------
        ShortestPath:list(int)
            shortest path
        """
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]


'''
ABC051-D
N頂点M辺の重み付き無向連結グラフがあり、
頂点a_iから頂点b_iを重みc_iで結んでいる。
どの最短経路にも含まれない辺の数を求めよ。

term:
2<=N<=100
N-1<=M<=min(N(N-1)/2,1000)
1<=a_i,b_i<=N
1<=c_i<=10**3

input:
3 3
1 2 1
1 3 1
2 3 3

output:
    1
'''

N, M = map(int, input().split())
graph = Dijkstra()
for i in range(M):
    a, b, c = map(int, input().split())
    graph.add(a, b, c, directed=False)

usedPaths = collections.defaultdict(set)
for i in range(1,N+1):
    for j in range(i+1, N+1):
        path = graph.getDijkstraShortestPath(i, j)
        if len(path) == 2:
            usedPaths[path[0]].add(path[1])
            usedPaths[path[1]].add(path[0])
        else:
            for idx, v in enumerate(path[:-1]):
                usedPaths[v].add(path[idx + 1])
                usedPaths[path[idx + 1]].add(v)

ans = M - sum([len(a) for a in list(usedPaths.values())])//2
print(ans)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

INF = 1 << 28
ds = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
    ds[i][i] = 0

for abc in ABC:

    ds[abc[0]][abc[1]] = ds[abc[1]][abc[0]] = min(ds[abc[0]][abc[1]], abc[2])

for k in range(N + 1):
    for i in range(N + 1):
        for j in range(N + 1):
            ds[i][j] = ds[j][i] = min(ds[i][j], ds[i][k] + ds[k][j])
cnt = 0
for abc in ABC:
    used = False
    for i in range(N + 1):
        for j in range(N + 1):
            if ds[i][j] == ds[i][abc[0]] + abc[2] + ds[abc[1]][j]:
                used = True
    if not used:
        cnt += 1

print(cnt)

Solution (Python):
import heapq
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    dp = [[float("inf")] * N for _ in range(N)]
    edges = list()
    for i in range(N):
        dp[i][i] = 0

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

    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = dp[i][k] + dp[k][j]
                if tmp < dp[i][j]:
                    dp[i][j] = tmp

    ans = 0
    for i, j, c in edges:
        if dp[i][j] < c:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, M = map(int, input().split())
    S = []

    d = [[float("inf")] * N for _ in range(N)]
    L = []
    for i in range(M):
        a, b, c = map(int, input().split())
        d[a - 1][b - 1] = c
        d[b - 1][a - 1] = c
        if a < b:
            L.append((a - 1, b - 1))
        else:
            L.append((b - 1, a - 1))
    for i in range(N):
        d[i][i] = 0
    L = set(L)

    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]
                        if i < j:
                            if (i, j) in L:
                                S.append((i, j))
                        else:
                            if (j, i) in L:
                                S.append((j, i))
        return d

    warshall_floyd(d)
    print(len(set(S)))


if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappop, heappush

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

graph = [[] for _ in range(N)]
for a, b, c in X:
    graph[a - 1].append((b - 1, c))
    graph[b - 1].append((a - 1, c))


def dijkstra(s):
    inf = 10 ** 9 + 7
    d = [inf] * N
    d[s] = 0
    pq = []
    heappush(pq, (0, s))
    while pq:
        _, u = heappop(pq)
        for v, c in graph[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heappush(pq, (d[v], v))

    return d


dist = [dijkstra(s) for s in range(N)]
ans = [False] * M
for n, (a, b, c) in enumerate(X):
    for i in range(N):
        for j in range(N):
            ans[n] |= dist[i][j] == dist[i][a - 1] + c + dist[j][b - 1]

print(M - sum(ans))

Solution (Python):
from collections import defaultdict
  
n,m = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(m)]
INF = 10 ** 18
d = [[INF] * n for i in range(n)]
for i in range(n):
  d[i][i] = 0
road = defaultdict(int)
for a,b,c in abc:
  a -= 1
  b -= 1
  road[(a, b)] = 1
  d[a][b] = c
  d[b][a] = c

for k in range(n):
  for i in range(n):
    for j in range(n):
      if d[i][k] + d[k][j] < d[i][j]:
        d[i][j] = d[i][k] + d[k][j]
        road[(i,j)] = 0
        road[(j,i)] = 0
ans = m - sum(road.values())
print(ans)

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import defaultdict
import sys
input = lambda: sys.stdin.readline().rstrip()
INF = 10**12
edges = defaultdict(lambda: defaultdict(lambda: INF))
n, m = map(int, input().split())
for i in range(m):
    a, b, c =map(int, input().split())
    edges[a-1][b-1] = (c, i)
    edges[b-1][a-1] = (c, i)

def dijkstra(s, n, w, cost):
    
    
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    que = [[0, s]] 
    prev = {}
    heapify(que)
    while len(que) > 0:
        u_dist, u = heappop(que)
        
        for v in cost[u].keys():
            alt = d[u] + cost[u][v][0]
            edge_num = cost[u][v][1]
            if d[v] > alt:
                prev[v] = (u, edge_num)
                d[v] = alt
                heappush(que, [alt, v])
    cnt = defaultdict(int)
    for goal in range(s, n):
        if goal == s:
            continue
        u = goal
        while u != s:
            cnt[prev[u][1]] += 1
            u = prev[u][0]
    return cnt

ans = set()
cnt_paths = defaultdict(int)
for start in range(n-1):
    cnt = dijkstra(start, n, m, edges)
    for k, v in cnt.items():
        cnt_paths[k] += v
    ans = ans | set(cnt_paths.keys())
print(m - len(ans))

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

a = [0]*M
b = [0]*M
c = [0]*M

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

d = [[float("inf")]*N for i in range(N)]

for i in range(M):
    d[a[i]][b[i]] = c[i]
    d[b[i]][a[i]] = c[i]
    
for i in range(N):
    d[i][i] = 0

for s in range(N):
    for j in range(N):
        for i in range(N):
            d[i][j] = min(d[i][j], d[i][s]+d[s][j])

count = 0
for i in range(M):
    if d[a[i]][b[i]] < c[i]:
        count += 1
print(count)

Solution (Python):
import copy
def warshall_floyd(d):
    cnt = 0
    d_first = copy.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])
    for i in range(len(d)):
        for fir, rev in zip(d_first[i], d[i]):
            if (rev < fir) and fir != float('inf'):
                cnt += 1
    return cnt//2

if __name__ == '__main__':
    n,w = map(int,input().split()) 

    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
    for i in range(n):
        d[i][i] = 0 
    print(warshall_floyd(d))

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

e = [[float('inf')]*n for i in range(n)]
for i in range(m):
    a, b,c = map(int, input().split())
    e[a-1][b-1]=c
    e[b-1][a-1]=c


ans=[[float('inf')]*n for i in range(n)]
d=copy.deepcopy(e)

def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i==j or k==i or k==j:
                    continue
                if d[i][j]==float('inf') and (d[i][k]==float('inf') or d[k][j]==float('inf')):
                    continue
                else:
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j]=d[i][k]+d[k][j]

warshall_floyd(d)
x=0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float('inf'):
            if e[i][j]>d[i][j]:
                x+=1
print(x//2)

Solution (Python):
def resolve():
    from scipy.sparse.csgraph import shortest_path
    import scipy
    import numpy as numpy
    n, m = map(int, input().split())
    row = [None] * m
    col = row[:]
    data = row[:]
    for i in range(m):
        row[i], col[i], data[i] = map(int, input().split())
        row[i] -= 1
        col[i] -= 1
    a = scipy.sparse.csr_matrix((data, (row, col)), shape=(n, n)).toarray()
    s, p = shortest_path(a, return_predecessors=True, directed=False)
    l = [[True] * n for _ in range(n)]
    for start in range(n - 1):
        for goal in range(start + 1, n):
            path = get_path(start, goal, p)
            for i in range(len(path) - 1):
                l[path[i]][path[i + 1]] = False
                l[path[i + 1]][path[i]] = False
    ans = 0
    for i, j in zip(row, col):
        if l[i][j]:
            ans += 1
    print(ans)


def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


resolve()

Solution (Python):
N, M = map(int,input().split())
INF = float('inf')
edges = []
for _ in range(M):
    edges.append(list(map(int,input().split())))
graph = [[INF if i != j else 0 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b, c = edges[i]
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for k in range(N):
    for i in range(N):
        for j in range(N):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
ans = 0
for i in range(M):
    a, b, c = edges[i]
    if c != graph[a-1][b-1]:
        ans += 1
print(ans)

Solution (Python):


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

nim,mike = map(int,input().split())

array = [[int(x) for x in input().split()] for _ in range(mike)]

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

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

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

Solution (Python):
def main():
    import sys
    
    readlines = sys.stdin.readlines
    N, M = map(int, input().split())
    edge = []
    dp = [[10 ** 9] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
    for s in readlines():
        a, b, c = map(int, s.split())
        a -= 1; b -= 1
        edge.append((a, b, c))
        dp[a][b] = c
        dp[b][a] = c
    
    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])

    cnt = 0
    for a, b, c in edge:
        if dp[a][b] < c:
            cnt += 1
    
    print(cnt)


if __name__ == "__main__":
    main()

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

def WarshallFloyd(M):
    N = len(M)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M


N, M, *ABC = map(int, open(0).read().split())

E = [[INF] * (N + 1) for _ in range(N + 1)]
for a, b, c in zip(*[iter(ABC)] * 3):
    E[a][b] = c
    E[b][a] = c

D = WarshallFloyd(E)

print(sum(D[a][b] < c for a, b, c in zip(*[iter(ABC)] * 3)))

Solution (Python):
n,m = map(int,input().split())
graph = [[float("inf")]*(n+1) for _ in range(n+1)]
for i in range(m):
  a,b,c = map(int,input().split())
  graph[a][b] = c
  graph[b][a] = c

    

def dijkstra(s,cost):
  d = [float("inf")]*(n+1)
  used = [False]*(n+1)
  d[s] = 0
  
  while True:
    v = -1
    for i in range(1,n+1):
      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(1,n+1):
      d[j] = min(d[j],d[v]+cost[v][j])
  return d

ans = 0
for i in range(1,n):
  d = dijkstra(i,graph)
  for j in range(i+1,n+1):
    if i == j:
      continue
    if graph[i][j] != float("inf") and graph[i][j] > d[j]:
      ans += 1
print(ans)