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 heapq
def dijkstra_heap(s,g):
    used = [True] * n 
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,[e[0],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        if v==g:
            return minedge[0]
        kai=minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return -1


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

edge = [[] for i in range(n)]

pp=[]
for i in range(m):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
    pp.append([x-1,y-1,z])
ans=0
for i in range(m):
    if pp[i][2]>dijkstra_heap(pp[i][0],pp[i][1]):
        ans+=1
print(ans)

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = {}
for i in range(m):
    a,b,c = inm()
    if a not in dst:
        dst[a] = {}
    dst[a][b] = c
    if b not in dst:
        dst[b] = {}
    dst[b][a] = c
d = [[BIG]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    d[i][i] = 0
    for j in dst[i]:
        d[i][j] = dst[i][j]
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])
sm = 0
for i in range(1,n):
    for j in range(i+1,n+1):
        if j in dst[i] and dst[i][j]>d[i][j]:
            sm += 1
print(sm)

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

wf=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c = l[i]
    wf[a-1][b-1] = c
    wf[b-1][a-1] = c
for i in range(n):
    wf[i][i]=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            wf[i][j] = min(wf[i][j],wf[i][k]+wf[k][j])

ans=0
for edge in l:
    ok=False
    for i in range(n):
        for j in range(n):
            dist = wf[i][j]
            if dist == wf[i][edge[0]-1] + edge[2] + wf[edge[1]-1][j]:
                ok=True
    if not ok:
        ans+=1
print(ans)

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

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

if __name__ == "__main__":
    n,e = map(int,readline().split()) 
    matrix = [[float("inf") for i in range(n)] for j in range(n)]
    lst1 = []
    for i in range(e):
        x,y,w = map(int,readline().split())
        x,y = x-1,y-1
        matrix[x][y] = w
        matrix[y][x] = w
        lst1.append([x,y,w])
    for i in range(n):
        matrix[i][i] = 0
    matrix = warshall_floyd(matrix)

    ans = 0

    
    for i in range(e):
        flag = True
        for j in range(n):
            for k in range(n):
                if matrix[j][k] == matrix[j][lst1[i][0]] + lst1[i][2] + matrix[lst1[i][1]][k]:
                    flag = False
        if flag:
            ans += 1
    print(ans)

Solution (Python):
from copy import deepcopy


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

INF = 10**9
N, M = map(int, input().split())
G = [[INF] * N for _ in range(N)]
for i in range(N):
    G[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G[a][b] = G[b][a] = c
dist = deepcopy(G)
floyd_warshall(dist)
used = set()
for i in range(N-1):
    checked = set()
    for j in range(i+1, N):
        stack = [j]
        while stack:
            v = stack.pop()
            if v in checked:
                continue
            checked.add(v)
            for k in range(N):
                if v == k:
                    continue
                if G[k][v] == INF:
                    continue
                if dist[i][v] == dist[i][k] + G[k][v]:
                    stack.append(k)
                    used.add((k, v) if k < v else (v, k))
print(M - len(used))

Solution (Python):
import copy
n, m = map(int ,input().split())
inf = 10**8
edges = []
graph = [[inf for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    a,b,c = map(int, input().split())
    graph[a][b] = graph[b][a] = c
    edges.append([a,b,c])
ans = 0
for i in range(n+1):
    graph[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 graph[i][k] + graph[k][j] < graph[i][j]:
                graph[i][j] = graph[i][k] + graph[k][j]
for i in range(m):
    flag = False
    a,b,c = edges[i]
    for j in range(1,n+1):
        for k in range(1,n+1):
            if graph[j][a] + c + graph[b][k] == graph[j][k]:
                flag = True
    if flag:
        ans += 1
print(m-ans)

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

DP = [[10**5 for _ in range(n)] for _ in range(n)]
for i in range(n):
    DP[i][i] = 0

Edge = []
for _ in range(m):
    a, b, c = map(int, input().split())
    DP[a-1][b-1] = c
    DP[b-1][a-1] = c
    Edge.append((a,b,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])

Edge_check = [0 for _ in range(len(Edge))]
for e in range(len(Edge)):
    for s in range(n):
        for t in range(n):
            if s == t:
                continue
            i = Edge[e][0] -1
            j = Edge[e][1] -1
            cost = Edge[e][2]
            if DP[s][i] + cost + DP[j][t] == DP[s][t]:
                Edge_check[e] = 1

ans = len(Edge_check) - sum(Edge_check)
print(ans)

Solution (Python):
import heapq
def dijkstra(adj, start, goal=None):
    num = len(adj)          
    dist = [float('inf') for i in range(num)]  
    
    dist[start] = 0
    
    q = []
    heapq.heappush(q, (0, start))  
    while q:
        prov_cost, src = heapq.heappop(q)  
        
        
            
        
        for dest in range(num):
            cost = adj[src][dest]
            if cost != float('inf') and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost  
                
                heapq.heappush(q, (dist[dest], dest))
                
    return dist
n, m = map(int, input().split())
mat = [[float('inf')] * n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c
for i in range(n):
    mat[i][i] = 0
mat2 = []
for i in range(n):
    mat2.append(dijkstra(mat, i))
ans = 0
for i in range(n):
    for j in range(i, n):
        if mat[i][j] != float('inf') and mat[i][j] != mat2[i][j]:
            ans += 1
print(ans)
'''input
3 3
1 2 1
1 3 1
2 3 3
'''

Solution (Python):
import heapq


def dijkstra(adj, start, goal=None):
    num = len(adj)          
    dist = [float('inf') for i in range(num)]  
    prev = [float('inf') for i in range(num)]  

    dist[start] = 0
    
    q = []
    heapq.heappush(q, (0, start))  

    while q:
        prov_cost, src = heapq.heappop(q)  

        
        if dist[src] < prov_cost:
            continue

        
        for dest in range(num):
            cost = adj[src][dest]
            if cost != float('inf') and dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost  
                
                heapq.heappush(q, (dist[dest], dest))
                prev[dest] = src                      

    return dist


n, m = map(int, input().split())
mat = [[float('inf')] * n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    mat[a - 1][b - 1] = c
    mat[b - 1][a - 1] = c
for i in range(n):
    mat[i][i] = 0
mat2 = []
for i in range(n):
    mat2.append(dijkstra(mat, i))
ans = 0
for i in range(n):
    for j in range(i, n):
        if mat[i][j] != float('inf') and mat[i][j] != mat2[i][j]:
            ans += 1
print(ans)

Solution (Python):
import heapq
import sys

input = sys.stdin.readline

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

used = [False] * (M + 1)


def dijkstra(start):
    inf = 10**18
    dist = [inf] * (N + 1)
    visited = [False] * (N + 1)
    dist[start] = 0
    visited[start] = False
    node = [(0, start, 0)]
    while node:
        d, s, e = heapq.heappop(node)
        if dist[s] < d:
            continue
        used[e] = True

        for t, cost, ind in edge[s]:
            if dist[t] > d + cost:
                dist[t] = d + cost
                heapq.heappush(node, (d + cost, t, ind))
    return


for i in range(1, N + 1):
    dijkstra(i)

ans = used.count(False)
print(ans)

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

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
ABC = np.array(read().split(), dtype=np.int64).reshape(m, 3)
A, B, C = ABC.T
csr = csr_matrix((C, (A, B)), shape=(n+1, n+1))
F = floyd_warshall(csr, directed=False)
ans = 0
for a, b, c in ABC:
  if c != F[a, b]:
    ans += 1
print(ans)

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


def dijkstra(x):
    dis = [float("inf")]*n
    dis[x] = 0
    q = []
    heapq.heappush(q,(0,x))
    
    while q:
        cost,bef = heapq.heappop(q)

        if dis[bef] < cost:
            continue

        for ncost,nex in E[bef]:
            dist = ncost+cost

            if dist < dis[nex]:
                dis[nex] = dist
                heapq.heappush(q,(dist,nex))
    return dis

short = []
for i in range(n):
    short.append(dijkstra(i))
count = 0
for i in range(n):
    for dist,nex in E[i]:
        if short[i][nex] < dist:
            count += 1
print(count//2)

Solution (Python):









import heapq
def initial_signal(i,adj,N):
    d = [float("inf") for _ in range(N)]
    d[i] = 0
    Q = [(0,i)]
    return d,Q

def relax(n_cost, u, v, adj,d,Q):
    if d[v] > d[u]+n_cost:
        d[v]=d[u]+n_cost
        heapq.heappush(Q,(d[v],v))



def dijkstra(i,adj,N):
    d,Q = initial_signal(i,adj,N)
    while Q:
        cost, u = heapq.heappop(Q)
        for n_cost, v in adj[u]:
            relax(n_cost, u, v, adj, d, Q)
        
    return d



def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = map(int, input().split())
        adj[a-1].append((c,b-1))
        adj[b-1].append((c,a-1))
    shortest = []
    for i in range(N):
        shortest.append(dijkstra(i,adj,N))
    ans = 0
    for i in range(N):
        for cost, j in adj[i]:
            if cost>shortest[i][j]:
                ans+=1
    print(ans//2)


if __name__ == "__main__":
    main()

Solution (Python):

import heapq

def dijkstra(graph, node, start):
    dist = [float("inf") for _ in range(node)]
    
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    
    while q:
        cost, cur_node = heapq.heappop(q)
        
        if dist[cur_node] < cost:
            continue
        
        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
                heapq.heappush(q, (dist[nex_node], nex_node))

    return dist

def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]
    for i in range(m):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append((c, b))
        adj[b].append((c, a))
    shortest = []
    for i in range(n):
        shortest.append(dijkstra(adj, n, i))
    ans = 0
    for i in range(n):
        for cost, j in adj[i]:
            if cost > shortest[i][j]:
                ans += 1
    print(ans // 2)
                                                                                                                                                                                                     
if __name__=='__main__':
    main()

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

d = [[1001] * n for i in range(n)]

es = []
for i in range(m):
    es.append(list(map(int, input().split())))

for (i, j, w) in es:
    d[i - 1][j - 1] = w
    d[j - 1][i - 1] = w


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

c = 0
for (i, j, w) in es:
    if d[i - 1][j - 1] < w:
        c += 1

print(c)

Solution (Python):
from scipy.sparse.csgraph import shortest_path
N, M = map(int, input().split())
dic = [[0]*N for i in range(N)]
Els = []
for i in range(M):
  a, b, c = map(int, input().split())
  dic[a-1][b-1] = c
  dic[b-1][a-1] = c
  Els += [(a-1,b-1,c)]
d, p = shortest_path(dic, return_predecessors=True, method='D')

ans = 0
for a, b, c in Els:
  if p[a][b]!=a:
    ans += 1
print(ans)

Solution (Python):
import numpy as np

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

d = np.ones((n, n)) * 1001

es = []
for i in range(m):
    es.append(list(map(int, input().split())))

for (i, j, w) in es:
    d[i - 1][j - 1] = w
    d[j - 1][i - 1] = w


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

c = 0
for (i, j, w) in es:
    if d[i - 1][j - 1] < w:
        c += 1

print(c)

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop
N, M = map(int, input().split())
dic = defaultdict(list)
Els = []
for i in range(M):
  a, b, c = map(int, input().split())
  dic[a-1] += [(b-1,c)]
  dic[b-1] += [(a-1, c)]
  Els += [(a-1,b-1,c)]

def dijkstra(s,e):
  dist = [float('inf')]*N
  dist[s] = 0
  q = [(0,s)]
  z = -1
  while q:
    c, v = heappop(q)
    if dist[v]<c:
      continue
    dist[v] = c
    for u, m in dic[v]:
      if dist[u]>dist[v]+m:
        dist[u] = dist[v]+m
        heappush(q,(dist[u],u))
        if u==e:
          z = v
  return z

ans = 0
for a, b, c in Els:
  if dijkstra(a,b)!=a:
    ans += 1
print(ans)

Solution (Python):
import heapq
class Graph():
    def __init__(self,vertex_num,node_num,naive_input,start_zero=True,direction=False):
        self.vertex_num=vertex_num
        self.node_num=node_num
        
        
        node=[{} for _ in range(vertex_num)]
        for i in range(node_num):
            u,v,w=naive_input[i]
            if not start_zero:
                u-=1
                v-=1
            node[u][v]={"weight":w,"index":i}
            
            if not direction:
                node[v][u]={"weight":w,"index":i}
                
        self.node=node
        
        self.node_num_arr=list(map(lambda x:len(x),node))

    def djikstra(self,s=0):
        distance=[float("inf") for _ in range(self.vertex_num)]
        distance[s]=0
        
        
        
        
        visited_vertex={s}
        before_vertex=[float("inf") for _ in range(self.vertex_num)]
        node_index_arr=[float("inf") for _ in range(self.vertex_num)]
        while len(visited_vertex)<self.vertex_num:
            
            will_visit_node=set()
            for now_node_num in visited_vertex:
                for next_node_num in self.node[now_node_num].keys():
                    if next_node_num in visited_vertex:
                        continue
                    will_visit_node.add(next_node_num)
                    next_node=self.node[now_node_num][next_node_num]
                    cal_d=distance[now_node_num]+next_node["weight"]
                    if cal_d<distance[next_node_num]:
                        distance[next_node_num]=cal_d
                        before_vertex[next_node_num]=now_node_num
                        node_index_arr[next_node_num]=next_node["index"]
                    
                    
            
            add_vertex=[float("inf"),float("inf")]
            for i in will_visit_node:
                if distance[i]<add_vertex[1]:
                    add_vertex[0]=i
                    add_vertex[1]=distance[i]
            visited_vertex.add(add_vertex[0])
        return node_index_arr
        





n,m=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(m)]
G=Graph(n,m,a,start_zero=False)  
ans=[True for _ in range(m)]
for i in range(n):
    tmp=G.djikstra(i)
    for j in tmp:
        if j!=float("inf"):
            ans[j]=False

print(sum(ans))

Solution (Python):
from scipy.sparse.csgraph import shortest_path
import numpy as np
N,M=map(int,input().split())
abc = [tuple(map(int,input().split())) for i in range(M)]
g = [[10**9]*N for i in range(N)]
for a,b,c in abc:
  a,b = a-1,b-1
  g[a][b]=c
  g[b][a]=c
g = np.array(g)
G,P=shortest_path(g,return_predecessors=True)
ans=set()
for i in range(N):
  for j in range(N):
    if P[i][j]>0 and (P[i][j],j) not in ans:
      ans.add((j,P[i][j]))

print(M-len(ans))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import heapq
import bisect
import copy
import math
from collections import defaultdict

def warshall_floyd(d, N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i * N +j] = min(d[i * N +j], d[i * N + k] + d[k * N + j])
    return d
MOD = 10**9 + 7
INF = 10**10

def dijkstra(n, graph, start):
    visited = [0 for i in range(n)]
    cost = [INF for i in range(n)]
    parents = [[] for i in range(n)]
    visited[start] = 1
    cost[start] = 0
    
    pq = []
    for g in graph[start]:
        heapq.heappush(pq, g)
    while(pq):
        nxt = heapq.heappop(pq)
        
        
        tcos, cur, tdist = nxt
        if cost[tdist] == cost[cur] + tcos:
            parents[tdist].append(cur)
        elif cost[tdist] > cost[cur] + tcos:
            cost[tdist] = cost[cur] + tcos
            parents[tdist] = [cur]
            for g in graph[tdist]:
                heapq.heappush(pq, g)

    res = []
    
    for i, par in enumerate(parents):
        for ppar in par:
            res.append((i, ppar))

    return res


def main():
    n, m = getlist()
    graph = [[] for i in range(n)]

    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))
        graph[b - 1].append((c, b-1, a-1))

    cands = []

    for start in range(n):
        res = dijkstra(n, graph, start)
        
        for re in res:
            if re[0] < re[1]:
                cands.append(re)
            else:
                cands.append((re[1], re[0]))

    print(m - len(list(set(cands))))

if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

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

INF = 10 ** 18
N, M = map(int, input().split())
d = [[INF for _ in range(N)] for _ in range(N)]
abc = []

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

wf = floyd_warshall(d)
cnt = 0
for i in range(M):
    if abc[i][2] > wf[abc[i][0]][abc[i][1]]:
        cnt += 1


print(cnt)

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

D=[[INF]*N for _ in range(N)]
for a,b,c in E:
    D[a][b]=D[b][a]=c
for z in range(N):
    for x in range(N):
        Dx=D[x]
        for y in range(N):
            Dx[y]=min(Dx[y], Dx[z]+D[z][y])

ans=M
for a,b,c in E:
    if D[a][b]==c: ans-=1
print(ans)

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

ans=[1]*M

import heapq
def dijkstra(s):
    distance=[-1]*N
    parent_n=[-1]*N
    parent_e=[-1]*N
    distance[s]=0
    parent_n[s]=s
    q=[(0,s)]
    while q:
        nc,n=heapq.heappop(q)
        for to,c,eid in E[n]:
            if distance[to]<0 or nc+c<distance[to]:
                distance[to]=nc+c
                parent_n[to]=n
                parent_e[to]=eid
                heapq.heappush(q,(nc+c,to))
    checked=[False]*N
    checked[s]=True
    for i in range(N):
        if checked[i]: continue
        n=i
        while n!=s:
            checked[n]=True
            ans[parent_e[n]]=0
            n=parent_n[n]

for i in range(N): dijkstra(i)
print(sum(ans))

Solution (Python):
from scipy.sparse.csgraph import dijkstra as di

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

g = di(grid)
ans = 0
for a,b,c in edges:
    if g[a][b] < c:
        ans += 1
print(ans)

Solution (Python):
import copy
N, M = map(int, input().split())
dp = [[float('inf')]*N for _ in range(N)]
ms = []
for i in range(N):
    dp[i][i] = 0

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

g = copy.deepcopy(dp)


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


ans = M
for m in ms:
    a, b, c = m
    for n in range(N):
        if dp[n][b] == (dp[n][a]+c):
            ans -= 1
            break
print(ans)

Solution (Python):
from copy import deepcopy
N, M = map(int, input().split())

graph = [[float('infinity')] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c
ans = 0


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

original = deepcopy(graph)

def warshall_floyd(graph, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

warshall_floyd(graph, N)

ans = 0
for i in range(N):
    for j in range(i):
        if original[i][j] != float('infinity') and graph[i][j] != original[i][j]:
            ans += 1
print(ans)

Solution (Python):
INF = 10**10
N,M=map(int,input().split())
e=[]
w=[[INF for j in range(N)]for i in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    w[a-1][b-1]=c
    w[b-1][a-1]=c
    e.append((a-1,b-1,c))

class lheapq():

    def __init__(self,p):
        self.l = []
        if p:
            for sp in p:
                self.heappush(sp)

    def heappush(self,a):
        n=len(self.l)
        self.l.append(a)
        t = n
        while t != 0:
            if self.l[t][1] < self.l[(t-1)//2][1]:
                self.l[t],self.l[(t-1)//2] = self.l[(t-1)//2],self.l[t]
                t = (t-1)//2
            else:break

    def heappop(self):
        n=len(self.l)
        if n == 0:
            return (-1,0)
        if n == 1:
            return self.l.pop()
        ret = self.l[0]
        self.l[0] = self.l.pop()
        n -= 1
        t = 0
        while t<n:
            child1 = t*2+1
            child2 = t*2+2
            if child1 >= n:
                break
            elif child2 >= n:
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t],self.l[child1] = self.l[child1],self.l[t]
                    t = child1
                else:break
            else:
                if self.l[child2][1] < self.l[child1][1]:
                    child1,child2 = child2,child1
                if self.l[t][1] > self.l[child1][1]:
                    self.l[t],self.l[child1] = self.l[child1],self.l[t]
                    t = child1
                elif self.l[t][1] > self.l[child2][1]:
                    self.l[t],self.l[child2] = self.l[child2],self.l[t]
                    t = child2
                else:break
        return ret
    
    def isnotblank(self):
        if self.l:return True
        else:return False

def dijkstra(s,g,N,e):
    INF =10**10
    res = [INF for _ in range(N)]
    q=lheapq([(s,0)])
    while q.isnotblank():
        while q.isnotblank():
            des,dis = q.heappop()
            if res[des] == INF:
                res[des] = dis
                break
        for se in e[des]:
            if res[se[0]] == INF:
                q.heappush((se[0],se[1]+res[des]))
    return res[g]

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

res = 0
for i in range(M):
    g=[[] for _ in range(N)]
    for j in range(M):
        if j!=i:
            a,b,c = e[j][0],e[j][1],e[j][2]
            g[a].append((b,c))
            g[b].append((a,c))
    a,b,c = e[i][0],e[i][1],e[i][2]
    if c != w[a][b] and dijkstra(a,b,N,g) == w[a][b]:
        res += 1

print(res)

Solution (Python):
from itertools import combinations
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
n,m = map(int,input().split())
abc = [list(map(int,input().split())) for i in range(m)]
abc = [[abc[i][0]-1,abc[i][1]-1,abc[i][2]] for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b,c in abc:
  graph[a].append((b,c))
  graph[b].append((a,c))
v1,v2,edge = zip(*abc)
csr = csr_matrix((edge,(v1,v2)),shape = (n,n))
dist = floyd_warshall(csr, directed = False)
ans = 0
for i,j in combinations(range(n),2):
  fs1,fs2 = zip(*graph[i])
  if j in fs1:
    x = fs1.index(j)
    if fs2[x] > dist[i][j]:
      ans += 1
print(ans)

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

def main():
    N, M = map(int, input().split())
    dist = [[float('inf') for i in range(N)] for j in range(N)]
    
    r = [[-1 for i in range(N)] for j in range(N)]
    
    for i in range(N): dist[i][i] = 0
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1; b -= 1
        dist[a][b] = c
        dist[b][a] = c
        
        r[a][b] = i
        r[b][a] = i
        
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dist[i][j] > dist[i][k]+dist[k][j]:
                    dist[i][j] = dist[i][k]+dist[k][j]
                    r[i][j] = r[k][j]
        
    ans = set()    
    for a in r: ans.update(set(a))    
    print(M-len(ans)+1)

if __name__ == '__main__':
    main()

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

def main():
    N, M = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(M)]
    INF = float("inf")
    D = [[INF] * N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for a, b, c in ABC:
        D[a-1][b-1] = c
        D[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    ans = M - sum(any(D[i][a-1] + c == D[i][b-1] for i in range(N)) for a, b, c in ABC)
    print(ans)


if __name__ == "__main__":
    main()