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 candidates_of_no_shortest_paths(N: int, M: int, edges: list)->int:
    INF = float('inf')

    d = [[0 if i == j else INF for i in range(N)] for j in range(N)]

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

    
    for k in range(N):
        for u in range(N):
            for v in range(N):
                if d[u][v] > d[u][k] + d[k][v]:
                    d[u][v] = d[u][k] + d[k][v]

    def used(edge: tuple)->bool:
        u, v, c = edge
        for s in range(N):
            if d[s][u-1] + c == d[s][v-1]:
                return True
        return False

    return sum(not used(edge) for edge in edges)


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    edges = [tuple(int(s) for s in input().split()) for _ in range(M)]
    ans = candidates_of_no_shortest_paths(N, M, edges)
    print(ans)

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

inf = float('inf')


def warshall_floyd(dist,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

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

warshall_floyd(ad,N)
ans = M

for a,b,c in edges:
    for s in range(N):
        if ad[s][a] + c == ad[s][b]:
            ans -= 1
            break

print(ans)

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

inf = float('inf')


def warshall_floyd(dist,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    dist[i][j] = 0
                elif dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

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

warshall_floyd(ad,N)
ans = M

for a,b,c in edges:
    if a > b:
        a,b = b,a
    for s in range(N):
        for e in range(s+1,N):
            if ad[s][a] + c + ad[b][e] == ad[s][e]:
                ans -= 1
                break
        else:
            continue
        break

print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop

def dijkstra(graph:list, node:int, start:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    heap = [(0,start)]
    
    
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

n,m = li()

edges = []
graph = [[] for _ in range(n)]
adj_mat = [[0]*n for _ in range(n)]

for _ in range(m):
    a,b,c = li()
    a -= 1
    b -= 1
    graph[a].append((c,b))
    graph[b].append((c,a))
    edges.append((a,b,c))
    

for i in range(n):
    adj_mat[i] = dijkstra(graph, n, i)
    
    

ans = 0
for ai, bi, ci in edges:
    if adj_mat[ai][bi] < ci:
        ans += 1
        
print(ans)

Solution (Python):
from collections import deque
from operator import itemgetter
n,m = map(int,input().split())
edge = [list(map(int,input().split())) for i in range(m)]

kyori =[[float("inf")]*n for i in range(n)]
for i in range(n):
  kyori[i][i] = 0
  
def dfs(start,goal):
  visited_cost = [float("inf")]*n
  visited_cost[start] = 0
  que = deque()
  que.append(start)
  while que:
    pos = que.pop()
    for [next_pos,cost] in tree[pos]:
      
      if visited_cost[next_pos] > visited_cost[pos] + cost:
        visited_cost[next_pos] = visited_cost[pos] + cost
        que.append(next_pos)    
  return visited_cost[goal]

edge = sorted(edge, key=itemgetter(2))
tree = [[] for i in range(n)]

ans = m
for [start,goal,cost] in edge:
  start -= 1
  goal -= 1
  if cost <= dfs(start,goal):
    tree[start].append([goal,cost])
    tree[goal].append([start,cost])
    ans -= 1
    
print(ans)

Solution (Python):
from copy import deepcopy
N,M=list(map(int, input().strip().split()))
abc={}
used={}
for _ in range(M):
    a,b,c=(list(map(int, input().strip().split())))
    abc[a,b]=c
    used[a,b]=False
spth=[[float("inf")]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    spth[i][i]=0
for ab,c in abc.items():
    spth[ab[0]][ab[1]]=c
    spth[ab[1]][ab[0]]=c
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            d=spth[i][k]+spth[k][j]
            if spth[i][j] > d:
                spth[i][j]=d

for ab,c in abc.items():
    for s in range(1,N+1):
        if used[ab]:break
        if spth[s][ab[1]]==spth[s][ab[0]]+c:
            used[ab]=True
            break
print(sum(not i for i in used.values()))

Solution (Python):
n,m=map(int,input().split())
a=[list(map(int,input().split()))for i in range(m)]
s=[[float("inf")]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    s[i][i]=0
for i in range(m):
    s[a[i][0]][a[i][1]]=a[i][2]
    s[a[i][1]][a[i][0]]=a[i][2]
for h in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if s[i][j]>s[i][h]+s[h][j]:
                s[i][j]=s[i][h]+s[h][j]
c=0
for i in range(m):
    for j in range(1,n+1):
        if s[j][a[i][0]]!=float("inf"):
            if s[j][a[i][0]]+a[i][2]==s[j][a[i][1]]:
                break
    else:
        c+=1
print(c)

Solution (Python):
n,M =map(int,input().split())
inf = 10**15

dist = [[inf for i in range(n)] for i in range(n)]
route = [[ [] for i in range(n)] for i in range(n)]
import copy

for i in range(M):
    ak,bk,ck = map(int,input().split())
    dist[ak-1][bk-1]  =ck
    dist[bk-1][ak-1]  =ck

for i in range(n):
    for k in range(n):
        route[i][k] = [i,k]
        route[k][i] = [k,i]


for a in range(n):
    for b in range(n):
        for c in range(n):
            
            if dist[b][a]+dist[a][c] < dist[b][c]:
                route[b][c] = copy.deepcopy(route[b][a]) + (copy.deepcopy(route[a][c])[1:])
                dist[b][c] =  dist[b][a]+dist[a][c]



    

used = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    for k in range(n):
        for m in range(len(route[i][k])-1):
            used[route[i][k][m]][route[i][k][m+1]] = 1
            used[route[i][k][m+1]][route[i][k][m]] = 1

    

ans = 0
for i in range(n):
    for k in range(n):
        if used[i][k]:
            ans += 1

print(M-(ans//2))

Solution (Python):
from scipy.sparse.csgraph import dijkstra
n, m = map(int, input().split())
edges = [[0]*n for i in range(n)]
query = []
ans = 0
for i in range(m):
    a,b,c = map(int, input().split())
    edges[a-1][b-1] = c
    edges[b-1][a-1] = c
    query.append([a-1, b-1, c])
for a,b,c in query:
    edges[a][b] = 0
    edges[b][a] = 0
    dist_ = dijkstra(edges, directed=False, indices=a)[b]
    if dist_ < c:
        ans += 1
    edges[a][b] = c
    edges[b][a] = c
print(ans)

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


inf = float("inf")
dist = [[inf] * N for _ in range(N)]

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

for mid in range(N):
  for start in range(N):
    for end in range(N):
      dist[start][end] = min(dist[start][end],
                 dist[start][mid] + dist[mid][end])

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

Solution (Python):
def main():
    N, M = map(int, input().split())
    adj = [[float("inf")] * (N) for _ in range(N)]
    path = [[[] for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj[a][b] = c
        adj[b][a] = c
        path[a][b].append((a, b))
        path[b][a].append((a, b))
    for i in range(N):
        adj[i][i] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if adj[i][k] + adj[k][j] < adj[i][j]:
                    adj[i][j] = adj[i][k] + adj[k][j]
                    path[i][j] = path[i][k] + path[k][j]
    used = set()
    for i in range(N):
        for j in range(N):
            for p in path[i][j]:
                used.add(p)
    print(M - len(used))


if __name__ == "__main__":
    main()

Solution (Python):

import sys
import copy

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[9999999 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	org = copy.deepcopy(maps)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])
				maps[j][i] = min(maps[i][j], maps[i][k] + maps[k][j])
			
	for i in range(N):
		for j in range(N):
			if i <= j:
				continue
			if org[i][j] == 9999999:
				continue
			if org[i][j] != maps[i][j]:
				ans += 1
		
	print(ans)
	
if __name__ == "__main__":
	main()

Solution (Python):

import sys
import copy

def main():
	N, M = map(int, input().split(" "))
	
	graph = []
	maps = [[9999999 for _ in range(N)] for _ in range(N)]
	for i in range(N):
		maps[i][i] = 0
	
	for _ in range(M):
		a, b, c = map(int, input().split(" "))
		a, b = a-1, b-1
		maps[a][b] = c
		maps[b][a] = c
	
	ans = 0
	org = copy.deepcopy(maps)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				
					
				if i <= j:
					continue
				maps[i][j] = min(maps[i][j], maps[i][k] + maps[k][j])
				maps[j][i] = min(maps[i][j], maps[i][k] + maps[k][j])
			
	for i in range(N):
		for j in range(N):
			if i <= j:
				continue
			if org[i][j] == 9999999:
				continue
			if org[i][j] != maps[i][j]:
				ans += 1
		
	print(ans)
	
if __name__ == "__main__":
	main()

Solution (Python):
def int_raw():
    return int(raw_input())
 
def ss_raw():
    return raw_input().split()
 
def ints_raw():
    return map(int,ss_raw())
 
INF = 1<<29
 
def make1d_arr(n,val=INF):
    return [val for i in xrange(n)]

def make2d_arr(w,h,val =INF):
    return [[val for i in xrange(w)]for i in xrange(h)]
 
def floyd_warshall(costs):
    N = len(costs)
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                costs[i][j]  = min(costs[i][j],costs[i][k]+costs[k][j])
    return costs
 
N,M = ints_raw()
costs = make2d_arr(N+1,N+1,INF)
E = []
for i in xrange(M):
    a,b,c = ints_raw()
    E.append((a,b,c))
    costs[a][b]=c
    costs[b][a]=c
 
costs = floyd_warshall(costs)
 
ans  = 0
for e in E:
    if costs[e[0]][e[1]] < e[2]:
        ans+=1
print ans

Solution (Python):
import heapq
class edge:
    def __init__(self,to,cost):
        self.to=to
        self.cost=cost

N,W=map(int,input().split())
G=[list() for i in range(N)]
for i in range(W):
    a,b,c=map(int,input().split())
    G[a-1].append(edge(b-1,c))
    G[b-1].append(edge(a-1,c)) 

def dijkstra(o):
    d=[float('inf') for i in range(N)]
    d[o]=0
    hq=[]
    prev=[[] for i in range(N)]
    heapq.heappush(hq,(0,o))
    while hq:
        p=heapq.heappop(hq)
        v=p[1]
        if(d[v]<p[0]):
            continue
        for i in G[v]:
            if(d[i.to]>d[v]+i.cost):
                d[i.to]=d[v]+i.cost
                prev[i.to]=prev[v]+[str(sorted([v,i.to]))]
                heapq.heappush(hq,(d[i.to],i.to))
    return d,prev


ans=set()
for i in range(N):
    tmp=dijkstra(i)[1]
    for j in tmp:
        if(j):
            ans.add(str(j[0]))
print(W-len(ans))

Solution (Python):
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())

INF = 1<<29

def make2d_arr(w,h,val =INF):
    return [[val]*w for i in xrange(h)]

def floyd_warshall(costs):
    N = len(costs)
    for k in xrange(N):
        for i in xrange(N):
            for j in xrange(N):
                costs[i][j]  = min(costs[i][j],costs[i][k]+costs[k][j])
    return costs

N,M = ints_raw()
costs = make2d_arr(N+1,N+1,INF)
E = []
for i in xrange(M):
    a,b,c = ints_raw()
    E.append((a,b,c))
    costs[a][b]=c
    costs[b][a]=c

costs = floyd_warshall(costs)

ans  = 0
for e in E:
    if costs[e[0]][e[1]] < e[2]:
        ans+=1
print ans

Solution (Python):
import heapq

n, m = map(int, input().split())
abc = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]

dist = [[9999999 for _ in range(n)] for _ in range(n)]

e = [dict() for _ in range(n)]

for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    e[a][b] = c + 1
    e[b][a] = c + 1

for i in range(n):
    h = []
    heapq.heappush(h, [0, i])
    temp = set()
    
    while len(temp) < n:
        d, p = heapq.heappop(h)
        while p in temp:
            d, p = heapq.heappop(h)
        dist[i][p] = d
        temp.add(p)
        for x in e[p].keys():
            heapq.heappush(h, [d + e[p][x], x])



ans = m
for a, b, c in abc:
    for i in range(n):
        if c + 1 == dist[a][i] - dist[b][i]:
            ans -= 1
            break
print(ans)

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

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

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

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

w = warshall_floyd(w)


res = 0
for i in range(n):
    for j in range(n):
        if w[i][j] == d[i][j]:
            res += 1
print(m-res//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):
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):
import heapq
n,m=map(int,input().split())
edges=[[] for _ in range(n)]
ABC=[]
for _ in range(m):
    a,b,c=map(int,input().split())
    a,b=a-1,b-1
    edges[a].append((b,c))
    edges[b].append((a,c))
    ABC.append([a,b,c])

def dijkstra(x,route):
    d=[float('inf')]*n
    d[x]=0
    visited={x}
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        visited.add(u)
        for node,cost in route[u]:
            if (node not in visited) and d[node]>d[u]+cost:
                d[node]=d[u]+cost
                heapq.heappush(hq,(d[node],node))
    return d

dist=[[] for _ in range(n)]
for i in range(n):
    dist[i]=dijkstra(i,edges)
ans=0
for a,b,c in ABC:
    if dist[a][b]!=c:
        ans+=1
print(ans)

Solution (Python):
def warshall_floyd(d, V, M): 
    for k in range(V):
        for i in range(V):
            for j in range(V):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                
    return d
    
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
dist = [[10 ** 5 for i in range(N)] for i in range(N)]

for l in L:
    l[0] -= 1
    l[1] -= 1
      
for i in range(M):
    dist[L[i][0]][L[i][1]] = L[i][2]
    dist[L[i][1]][L[i][0]] = L[i][2]

dist = warshall_floyd(dist, N, M)

res = 0

for i in range(M):
    if dist[L[i][0]][L[i][1]] != L[i][2]:
        res += 1
            
print(res)

Solution (Python):
def warshall_floyd(d, V, M): 
    for k in range(V):
        for i in range(V):
            for j in range(V):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
                
    return d
    
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
dist = [[10 ** 5 for i in range(N)] for i in range(N)]

for l in L:
    l[0] -= 1
    l[1] -= 1
      
for i in range(M):
    dist[L[i][0]][L[i][1]] = L[i][2]
    dist[L[i][1]][L[i][0]] = L[i][2]

dist = warshall_floyd(dist, N, M)

res = 0

for i in range(M):
    if dist[L[i][0]][L[i][1]] != L[i][2]:
        res += 1
            
print(res)

Solution (Python):
from collections import defaultdict


def dd(N, abc, ne_table, start_i):
    used_edge = set()
    pivot = start_i

    kouho = {start_i: (0, 0, True)}  

    for _ in range(N - 1):

        current_dist, path, kaku = kouho[pivot]
        assert kaku
        edges_i = ne_table[pivot]  
        for i in edges_i:
            a, b, weight = abc[i]
            target = a if a != pivot else b

            if target in kouho:
                tmp_d, tmp_path, kakutei = kouho[target]
                if kakutei:
                    continue
                if current_dist + weight < tmp_d:  
                    kouho[target] = (current_dist + weight, i, False)
                continue
            kouho[target] = (current_dist + weight, i, False)

        min_kouho = min([(k, d, p) for k, (d, p, kakutei) in kouho.items() if not kakutei], key=lambda q: q[1])
        min_kouho_i = min_kouho[0]
        used_edge.add(min_kouho[2])
        kouho[min_kouho_i] = (kouho[min_kouho_i][0], kouho[min_kouho_i][1], True)
        pivot = min_kouho_i
    return used_edge


def main():
    N, M = [int(a) for a in input().split()]

    def pre(a, b, c):
        return a - 1, b - 1, c

    abc = [
        pre(*[int(a) for a in input().split()])
        for _ in range(M)
    ]

    ne_table = defaultdict(lambda: [])
    for i, (a, b, c) in enumerate(abc):
        ne_table[a].append(i)
        ne_table[b].append(i)

    total_used = set()

    for i in range(N):
        used = dd(N, abc, ne_table, i)
        total_used.update(used)

    print(M - len(total_used))


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
from collections import *
d=defaultdict(list)
n,m=map(int,input().split())

for s in range(m):
    a,b,c=map(int,input().split())
    d[a].append([b,c])
    d[b].append([a,c])




def DIJKSTRA(point,d):
    cost      = {node:np.inf for node in d.keys()}
    preference= {node:  None for node in d.keys()}
    Q         = set(d.keys())  
    cost[point]=0  
    while True:
        prefnd=min(Q, key=lambda c:cost[c]) 
        Q.remove(prefnd)  
   
        if len(Q)==0:
            break 
        for pathcost in d[prefnd]:  
            tempcost=cost[prefnd]+pathcost[1]  
            if tempcost<cost[pathcost[0]]:   
                cost[pathcost[0]]=tempcost 
                preference[pathcost[0]]=prefnd
    return [tuple(sorted([k,v])) for k,v in preference.items() if v!=None]
path=[]
for s in range(1,n+1):
    path.extend(DIJKSTRA(s,d))
print(m-len(set(path)))

Solution (Python):
import sys

sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n,m=map(int,input().split())
g=[[]for i in range(n)]
s=set()
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1].append((c,b-1))
    g[b-1].append((c,a-1))
    if a>b:
        a,b=b,a
    s.add((a-1,b-1))

def dijkstra(g,st,s):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st,-1))
    while que:
        c,v,past=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        try:
            s.remove((v,past) if v<past else (past,v))
        except:
            pass
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1],v))

for i in range(n):
    dijkstra(g,i,s)
print(len(s))

Solution (Python):
import sys

sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n,m=map(int,input().split())
g=[[]for i in range(n)]
s=set()
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1].append((c,b-1))
    g[b-1].append((c,a-1))
    if a>b:
        a,b=b,a
    s.add((a-1,b-1))

def dijkstra(g,st,s):
    from heapq import heappush, heappop, heapify
    inf=10**18
    dist=[inf for i in range(len(g))]
    visited=[False for i in range(len(g))]
    dist[st]=0
    que=[]
    heappush(que,(0,st,-1))
    while que:
        c,v,past=heappop(que)
        if visited[v]:
            continue
        visited[v]=True
        try:
            s.remove((v,past) if v<past else (past,v))
        except:
            pass
        for x in g[v]:
            tmp=x[0]+c
            if tmp<dist[x[1]] and not visited[x[1]]:
                dist[x[1]]=tmp
                heappush(que,(tmp,x[1],v))

for i in range(n):
    dijkstra(g,i,s)
print(len(s))

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

inf = float("inf")
dist  =  [[inf] * N for _ in range(N)]

for i in range(M):
    dist[inp[i][0]][inp[i][1]] = inp[i][2]
    dist[inp[i][1]][inp[i][0]] = inp[i][2]

for mid in range(N):
    for start in range(N):
        for end in range(N):
            dist[start][end] = min(dist[start][end],
                    dist[start][mid] + dist[mid][end])


ans = 0
for ai,bi,ci in inp:
    if dist[ai][bi] != ci:
        ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
edge=[]
branch=[[] for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    edge.append((a-1,b-1,c))
    branch[a-1].append((b-1,c))
    branch[b-1].append((a-1,c))

dist=[]
def makedist(start,branch):
    check={start,}
    mind=[10**7 for i in range(n)]
    mind[start]=0
    while len(check)>0:
        now=check.pop()
        for k in branch[now]:
            if k[1]+mind[now]<mind[k[0]]:
                mind[k[0]]=k[1]+mind[now]
                check|={k[0],}
    return mind
for i in range(n):
    dist.append(makedist(i,branch))
ans=0
for k in edge:
    for s in range(n):
        if abs(dist[s][k[0]]-dist[s][k[1]])==k[2]:
            ans+=1
            break
print(m-ans)

Solution (Python):

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

dist = [[float('inf')]*N for _ in range(N)]
for i in range(M):
    dist[a[i]][b[i]] = c[i]
    dist[b[i]][a[i]] = c[i]

for mid in range(N):
    for start in range(N):
        for end in range(N):
            dist[start][end] = min(dist[start][end],
                                   dist[start][mid] + dist[mid][end])

ans = 0
for ai,bi,ci in zip(a,b,c):
    if dist[ai][bi]!=ci:
        ans += 1
print(ans)

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

import numpy as np
dists = np.ones((n + 1, n + 1)) * (10 ** 6)
edges = []
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
    edges.append((a, b, c))
for i in range(1, n + 1):
    dists[i, i] = 0
for i in range(1, 1 + n):
    dists = np.minimum(dists, dists[i: i + 1] + dists[:, i: i + 1])
cnt = 0
for a, b, c in edges:
    if dists[a, b] < c:
        cnt += 1

print(cnt)

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

import numpy as np
dists = np.ones((n + 1, n + 1)) * (10 ** 6)
edges = []
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
    edges.append((a, b, c))
for i in range(1, n + 1):
    dists[i, i] = 0
for i in range(1, 1 + n):
    dists = np.minimum(dists, dists[i: i + 1] + dists[:, i: i + 1])
cnt = 0
for a, b, c in edges:
    if dists[a, b] < c:
        cnt += 1

print(cnt)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall as fw
n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]

mapm = [[0] * (n) for _ in range(n)]
for i in abc:
    mapm[i[0] - 1][i[1] - 1] = i[2]
    mapm[i[1] - 1][i[0] - 1] = i[2]

f = fw(mapm)
count = 0
for i in abc:
    if f[i[0]-1][i[1]-1] != i[2]:
        count += 1

print(count)

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

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

ans =0
for i in range(N):
    for j in range(N):
        if i <= j:
            continue
        if cost[i][j] ==9999:
            continue
        if cost[i][j] != dist[i][j]:
            ans +=1

print(ans)

Solution (Python):
INFTY = (1<<32)

def floyd(n, d):
    for k in range(n):
        for i in range(n):
            if d[i][k] == INFTY:
                continue
            for j in range(n):
                if d[k][j] == INFTY:
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])


N, M = [int(i) for i in input().split()]

g = [[INFTY] * N for i in range(N)]
for i in range(N):
    g[i][i] = 0

edge_dict = {}
for i in range(M):
    a, b, c = [int(v) for v in input().split()]
    a -= 1
    b -= 1
    edge_dict[(a, b)] = c
    g[a][b] = c
    g[b][a] = c

floyd(N, g)

ans = M
for e, c in edge_dict.items():
    a, b = e
    for s in range(N):
        if g[s][a] + c == g[s][b]:
            ans -= 1
            break

print(ans)

Solution (Python):
N, M = map(int, input().split())
inf = float("inf")
dp = [[inf]*N for _ in [0]*N]
for i in range(N):dp[i][i] = 0
d = [list(map(int, input().split())) for i in range(M)]
ans = 0
from scipy.sparse.csgraph import floyd_warshall 
for a,b,c in d:
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
cost = floyd_warshall(dp)
for a,b,c in d:
        if cost[a-1][b-1] != c:
            ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
inf = float("inf")
dp = [[inf]*N for _ in [0]*N]
for i in range(N):dp[i][i] = 0
d = [list(map(int, input().split())) for i in range(M)]
ans = 0
 
for a,b,c in d:
    dp[a-1][b-1] = c
    dp[b-1][a-1] = 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])
for a,b,c in d:
        if dp[a-1][b-1] != c:
            ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
inf = float("inf")
dp = [[inf]*N for _ in [0]*N]
for i in range(N):dp[i][i] = 0
d = [list(map(int, input().split())) for i in range(M)]
ans = 0
 
for a,b,c in d:
    dp[a-1][b-1] = c
    dp[b-1][a-1] = 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])
for a,b,c in d:
        if dp[a-1][b-1] != c:
            ans += 1
print(ans)

Solution (Python):





from heapq import heappush, heappop

HUGE = 10 ** 15

def main():
    n, m = map(int, input().split())
    dist_sets = [{} for i in range(n)]
    for i in range(m):
        a1, b1, c = map(int, input().split())
        dist_sets[a1 - 1][b1 - 1] = c
        dist_sets[b1 - 1][a1 - 1] = c
    shortest_path_mat = [get_shortest_path_dijkstra(i, dist_sets) for i in range(n)]
    res = 0
    for i in range(n):
        for j in dist_sets[i].keys():
            if i > j:
                continue
            if shortest_path_mat[i][j] < dist_sets[i][j]:
                res += 1
    print(res)

def get_shortest_path_dijkstra(root, dist_sets):
    n = len(dist_sets)
    known_sp = [HUGE for i in range(n)]
    known_sp[root] = 0
    determined = [(i == root) for i in range(n)]
    pq = [(known_sp[root], root)]  
    while len(pq) > 0:
        sp_cand, i = heappop(pq)
        determined[i] = True
        if known_sp[i] < sp_cand:
            continue
        for j, dist_ij in dist_sets[i].items():
            if determined[j]:
                continue
            if known_sp[i] + dist_ij < known_sp[j]:
                known_sp[j] = known_sp[i] + dist_ij
                heappush(pq, (known_sp[j], j))
    return known_sp

main()