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

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    from collections import defaultdict
    from copy import copy
    n, m = map(int, readline().split())

    used = dict()
    for i in range(n):
        used[i] = dict()

    edge = defaultdict(list)

    for i in range(m):
        a, b, c = map(int, readline().split())
        edge[a].append((b, c))
        edge[b].append((a, c))
        if a < b:
            used[a][b] = False
        else:
            used[b][a] = False

    for i in range(1,n+1):
        dist = [100000000000] * (n+1)
        dist[i] = 0
        prev = defaultdict(list)
        hq = []
        heapq.heappush(hq, (0, i))
        while hq:
            cur, u = heapq.heappop(hq)
            for v, w in edge[u]:
                if dist[v] > cur + w:
                    dist[v] = cur + w
                    prev[v] = [u]
                    heapq.heappush(hq, (cur + w, v))
                elif dist[v] == cur + w:
                    prev[v].append(u)
                    heapq.heappush(hq, (cur + w, v))

        for v, val in prev.items():
            for u in val:
                if u < v:
                    used[u][v] = True
                else:
                    used[v][u] = True

    ans = 0

    for val in used.values():
        for x in val.values():
            if not x:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
es = []
for i in range(m):
    u,v,c = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add((c,v))
    ns[v].add((c,u))
    es.append((u,v,c))
    
def dijkstra(start):
    import heapq
    vals = [None] * n
    h = [(0, start)] 
    vals[start] = 0
    while h:
        val, u = heapq.heappop(h)
        for d, v in ns[u]:
            if vals[v] is None or vals[v]>val+d:
                vals[v] = val+d
                heapq.heappush(h, (vals[v], v))
    return vals
unused = [True]*m
for u in range(n):
    vals = dijkstra(u)
    for i,(a,b,c) in enumerate(es):
        if abs(vals[a]-vals[b])==c:
            unused[i] = False
ans = sum(unused)
print(ans)

Solution (Python):

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



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

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

edge=[]
for i in range(m):
    x,y,c = map(int,input().split())
    x-=1
    y-=1
    edge.append((x,y,c))
    d[x][y] = c
    d[y][x] = c
for i in range(n):
    d[i][i] = 0 
d=warshall_floyd(d)
ans=0
for x,y,c in edge:
    if d[x][y]<c:
        ans+=1
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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






N, M = getNM()
query = [getList() for i in range(M)]

dist = [[float('inf')] * N for i in range(N)]
for i in range(N):
    dist[i][i] = 0
for i in range(M):
    a, b, c = query[i]
    dist[a - 1][b - 1] = c
    dist[b - 1][a - 1] = c

def warshall_floyd(dist):
    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])
    return dist

warshall_floyd(dist)
ng_dist = [0] * M

for i in range(N):
    for j in range(M):
        s, t, c = query[j]
        if dist[i][s - 1] + c == dist[i][t - 1]:
            ng_dist[j] = 1

cnt = 0
for i in ng_dist:
    if i == 0:
        cnt += 1
print(cnt)

Solution (Python):
import heapq

def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        G[a - 1].append((b - 1, c))
        G[b - 1].append((a - 1, c))
    used = set()
    for i in range(N):
        H = []
        for b, c in G[i]:
            heapq.heappush(H, (c, i, b))
        D = [10**10] * N
        D[i] = 0
        while H:
            c, a, b = heapq.heappop(H)
            if D[b] < c:
                continue
            D[b] = c
            if a < b:
                used.add((a, b))
            else:
                used.add((b, a))
            for d, cc in G[b]:
                if D[d] > c + cc:
                    D[d] = c + cc
                    heapq.heappush(H, (c + cc, b, d))
    return M - len(used)

print(main())

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
def main():
    N, M = map(int, input().split())
    w = [[0] * N for i in range(N)]
    l = []
    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        w[a][b] = w[b][a] = c
        l.append((a,b,c))
    G = csr_matrix(w)
    d = floyd_warshall(G, directed=False)
    r = 0
    for a, b, c in l:
        if d[a][b] != c:
            r += 1
    return r
print(main())

Solution (Python):
class Graph():  
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j, cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist


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

g = Graph(N, E)
wf = g.warshall_floyd()

res = 0

for i in range(M):
    a, b, c = E[i]
    if wf[a - 1][b - 1] != c:
        res += 1

print(res)

Solution (Python):
import heapq


def dijkstra(n, s, g):
    h = [(0, s)]
    heapq.heapify(h)
    cost = [float("Inf")] * (n + 1)  
    cost[s] = 0

    while h:
        c, v = heapq.heappop(h)
        if c > cost[v]:
            continue
        for d, u in g[v]:
            d_s_u = d + cost[v]
            if d_s_u < cost[u]:
                cost[u] = d_s_u
                heapq.heappush(h, (d_s_u, u))

    return cost


def main():
    n, m, *abc = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for a, b, c in zip(*[iter(abc)] * 3):
        g[a].append([c, b])
        g[b].append([c, a])

    ans = 0
    checked = [[False] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        cost = dijkstra(n, i, g)
        for j, k in g[i]:
            if checked[i][k]:
                continue
            if j > cost[k]:
                ans += 1

            checked[i][k] = True
            checked[k][i] = True

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq


def dijkstra(n, s, g):
    h = [(0, s)]
    heapq.heapify(h)
    cost = [float("Inf")] * (n + 1)  
    cost[s] = 0

    while h:
        c, v = heapq.heappop(h)
        if c > cost[v]:
            continue
        for d, u in g[v]:
            d_s_u = d + cost[v]
            if d_s_u < cost[u]:
                cost[u] = d_s_u
                heapq.heappush(h, (d_s_u, u))

    return cost


def main():
    n, m, *abc = map(int, open(0).read().split())
    g = [[] for _ in range(n + 1)]

    for a, b, c in zip(*[iter(abc)] * 3):
        g[a].append([c, b])
        g[b].append([c, a])

    ans = 0
    for i in range(1, n + 1):
        cost = dijkstra(n, i, g)
        for j, k in g[i]:
            if j > cost[k]:
                ans += 1

    print(ans//2)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m, *abc = map(int, open(0).read().split())
    d = [[float("Inf")] * (n + 1) for _ in range(n + 1)]

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

    for a, b, c in zip(*[iter(abc)] * 3):
        d[a][b] = c
        d[b][a] = c

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

    ans = 0
    for a, b, c in zip(*[iter(abc)] * 3):
        if d[a][b] < c:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
E=[list(map(int,input().split())) for i in range(M)]
INF=10**12
D=[[INF]*N for i in range(N)]
for i in range(N):
  D[i][i]=0
for i in range(M):
  D[E[i][0]-1][E[i][1]-1]=E[i][2]
  D[E[i][1]-1][E[i][0]-1]=E[i][2]
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])
P=0
for i in range(M):
  for j in range(N):
    if D[j][E[i][0]-1]+E[i][2]==D[j][E[i][1]-1] or D[j][E[i][1]-1]+E[i][2]==D[j][E[i][0]-1]:
      break
    if j==N-1:
      P+=1
print(P)

Solution (Python):
n, m = map(int, input().split())
graph = [[10 ** 9 for _ in range(n)] for _ in range(n)]
edge = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a][b] = c
    graph[b][a] = c
    edge.append((a, b))
for i in range(n):
    graph[i][i] = 0

from copy import deepcopy
distance = deepcopy(graph)    
for k in range(n):
    for i in range(n):
        for j in range(n):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
ans = 0
for i, j  in edge:
    if distance[i][j] < graph[i][j]:
        ans += 1
print(ans)

Solution (Python):
def warshall_floyd(graph):
    n_nodes = len(graph)

    froms = []
    for i in range(len(graph)):
        froms.append([])
        for j in range(len(graph[i])):
            if i == j:
                froms[i].append(0)
            elif graph[i][j] < float("inf"):
                froms[i].append(i)
            else:
                froms[i].append(None)

    for k in range(n_nodes):
        for i in range(n_nodes):
            for j in range(n_nodes):
                adj_cost = graph[i][k] + graph[k][j]
                if adj_cost < graph[i][j]:
                    graph[i][j] = adj_cost
                    froms[i][j] = froms[k][j]
    
    has_negative_loop = False
    for i in range(n_nodes):
        if graph[i][i] < 0:
            has_negative_loop = True
            break

    return graph, froms, has_negative_loop

def restore_path(froms, start, goal):
    path = []
    cur = goal
    path.append(goal)
    while cur != start:
        prev = froms[start][cur]
        path.append(prev)
        cur = prev
    path.reverse()
    return path

def resolve():
    N, M = list(map(int, input().split()))
    graph = [[float("inf") for _ in range(N)] for __ in range(N)]
    import copy
    exists = [[False for _ in range(N)] for __ in range(N)]
    for i in range(M):
        a, b, c = list(map(int, input().split()))
        graph[a-1][b-1] = c
        graph[b-1][a-1] = c
        exists[a-1][b-1] = True
        exists[b-1][a-1] = True
    costs, froms, _ = warshall_floyd(graph)
    

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            path = restore_path(froms, i, j)
            
            
            src = 0
            for dst in range(1, len(path)):
                exists[path[src]][path[dst]] = False
                exists[path[dst]][path[src]] = False
                src = dst
    
    print(sum(sum(exists, []))//2)



if __name__ == '__main__':
    resolve()

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

Solution (Python):
n,m = map(int,input().split())
INF = 10**18
d = [[INF]*n for _ in range(n)]
nd = [[INF]*n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
    nd[i][i] = 0
for _ in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
    nd[a][b] = c
    nd[b][a] = c

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

cnt = 0
for i in range(n):
    for j in range(n):
        if d[i][j] == INF: continue
        if nd[i][j] < d[i][j]: cnt += 1
print(cnt//2)

Solution (Python):
import networkx as nx
import itertools

N, M = map(int, input().split())
G = nx.Graph()
G.add_nodes_from(range(1, N + 1))
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):
from heapq import heappop, heappush
from copy import deepcopy
def main():
    N, M = map(int, input().split())
    INF = 10**9
    to = [[INF]*N for _ in range(N)]
    edges = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        to[a][b] = c
        to[b][a] = c
        edges.append((a, b, c))
    
    for i in range(N): to[i][i] = 0

    def floyd_warshall():
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    to[i][j] = min(to[i][j], to[i][k]+to[k][j])
    
    floyd_warshall()
    ans = 0
    for a, b, c in edges:
        if to[a][b] != c:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n,m=map(int,input().split())
g=[[]for _ in range(n)]
for i in range(m):
  a,b,c=map(int,input().split())
  a,b=a-1,b-1
  g[a].append((c,b,i))
  g[b].append((c,a,i))
no_used=[1]*m
from heapq import heapify,heappop,heappush
def dks(t0):
  todo=[[0,t0,-1]]
  heapify(todo)
  seen=[0]*n
  while todo:
    d,t,i=heappop(todo)
    if seen[t] and seen[t]<d:continue
    seen[t]=d
    if i>-1:no_used[i]=0
    l=g[t]
    for d_,t_,i_ in l:
      heappush(todo,[d+d_,t_,i_])
for i in range(n):
  dks(i)
print(sum(no_used))

Solution (Python):






from collections import deque





n,m=map(int,input().split())
edge=[list(map(int,input().split())) for _ in range(m)]
           
inf=10**9
nextm=[[inf]*n for _ in range(n)]

for i in range(n):
    nextm[i][i]=0
for i in range(m):
    to,f,weight=edge[i]
    nextm[to-1][f-1]=weight
    nextm[f-1][to-1]=weight

for k in range(n):
    for i in range(n):
        for j in range(n):
            if nextm[i][j]>nextm[i][k]+nextm[k][j]:
                nextm[i][j]=nextm[i][k]+nextm[k][j]
res=0               
for i in range(m):
  a,b,c=edge[i]
  if c>nextm[a-1][b-1]:
    res+=1
print(res)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    cos = []
    row = []
    col = []
    for _ in range(m):
        a,b,c = map(int,ipt().split())
        row.append(a-1)
        col.append(b-1)
        cos.append(c)
    csr = csr_matrix((cos,(row,col)),shape=(n,n))
    d = dijkstra(csr,directed=False)
    ans = 0
    for i in range(m):
        rwi = row[i]
        cli = col[i]
        csi = cos[i]
        dri = d[rwi]
        dci = d[cli]
        for j in range(n):
            if dri[j] + csi == dci[j]:
                break
            if j == n-1:
                ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

Solution (Python):
import os,io
import heapq
INF=10**9
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline  
n,m=map(int,input().split())
edges=[]
d=[]
for i in range(n+1):
  d.append([])
  for j in range(n+1):
    d[-1].append(INF)
  d[i][i]==0
for i in range(m):
  a,b,c=list(map(int,input().split()))
  edges.append([a,b,c])
  d[a][b]=c
  d[b][a]=c
for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      if (d[i][j]>d[i][k]+d[k][j]):
        d[i][j]=d[i][k]+d[k][j]
ans=0
for i in range(m):
  a=edges[i][0]
  b=edges[i][1]
  c=edges[i][2]
  if d[a][b]<c:
    ans+=1
print(ans)

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

Solution (Python):
N,M=list(map(int,input().split()))
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
l=[np.array([0]*N) for i in range(N)]
for i in range(M):
   tmp=(list(map(int,input().split())))
   l[tmp[0]-1][tmp[1]-1]=tmp[2]
   l[tmp[1]-1][tmp[0]-1]=tmp[2]
l2=csr_matrix(l)
l2=floyd_warshall(l2)
ans=0
for i in range(N):
   for j in range(i):
      if l[i][j] != l2[i][j] and l[i][j] != 0:
         ans+=1
print(ans)

Solution (Python):
from collections import defaultdict
import heapq


INF = 10 ** 6


def check(N, adj_nodes, costs, from_node, to_node):
    
    dists = [INF for _ in range(N)]
    dists[from_node] = 0
    frontier = [(0, from_node)]
    while len(frontier) > 0:
        d, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            if (from_node, to_node) == (node, next_node):
                continue
            next_d = costs[node][next_node] + dists[node]
            if dists[next_node] > next_d:
                dists[next_node] = next_d
                heapq.heappush(frontier, (next_d, next_node))
    return costs[from_node][to_node] > dists[to_node]


def main():
    N, M = list(map(int, input().split(' ')))
    adj_nodes = defaultdict(list)
    costs = [[INF for _ in range(N)] for _ in range(N)]
    edges = list()
    for _ in range(M):
        a, b, c = list(map(int, input().split(' ')))
        a -= 1
        b -= 1
        adj_nodes[a].append(b)
        adj_nodes[b].append(a)
        costs[a][b] = c
        costs[b][a] = c
        edges.append((a, b))
    ans = 0
    for edge in edges:
        from_node, to_node = edge
        if check(N, adj_nodes, costs, from_node, to_node):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,m = map(int,input().split())
li = [[0 for i in range(n)]for j in range(n)]
lis = []

def all_pairs_shortest_paths(W):
    inf = 10**18
    
    n = len(W)
    
    res = [[0] * n for i in range(n)]
    
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

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

lin = all_pairs_shortest_paths(li)
point = 0

for path in lis:
    a,b,c = path
    flag = False
    for i in range(n):
        for j in range(n):
            if lin[i][a]+c+lin[b][j] == lin[i][j]:
                flag = True
    if not flag:
        point += 1

print(point)

Solution (Python):
from heapq import heappush, heappop

N, M = map(int, input().split())
INF = 10**10
edge_idx = {}
graph = [[] for i in range(N)]
for i in range(M):
  a, b, c = map(int, input().split())
  a -= 1; b -= 1
  graph[a].append((b, c))
  graph[b].append((a, c))
  edge_idx[(a, b)] = edge_idx[(b, a)] = i

used = set()
def dijkstra(node):
  global used
  dist = [INF] * N
  dist[node] = 0
  e = []
  for child, cost in graph[node]:
    heappush(e, (cost, child, node))
  while e:
    cost, node, par = heappop(e)
    if dist[node] < INF:
      if dist[node] == cost:
        used.add(edge_idx[(node, par)])
      continue
    dist[node] = cost
    used.add(edge_idx[(node, par)])
    for child, c in graph[node]:
      if dist[child] < INF:
        continue
      heappush(e, (cost+c, child, node))

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

print(M - len(used))

Solution (Python):
n, m = map(int, input().split())
a, b, c = zip(*[list(map(int, input().split())) for i in range(m)])

dist = [[1e18]*n for i in range(n)]
for i in range(m):
    dist[a[i]-1][b[i]-1] = dist[b[i]-1][a[i]-1] = min(dist[a[i]-1][b[i]-1], c[i])

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
ans = 0
for i in range(m):
    if dist[a[i]-1][b[i]-1]<c[i]:
        ans += 1

print(ans)

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline

    inf = 1000 * 100 + 10

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

    dist = [[inf for _ in range(N)] for _ in range(N)]
    for j in range(N):
        dist[j][j] = 0

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

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

    ans = 0
    for a, b, c in es:
        if dist[a][b] == c: continue
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline

    inf = 1000 * 100 + 10

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

    dist = [[inf for _ in range(N)] for _ in range(N)]
    for j in range(N):
        dist[j][j] = 0

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

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

    ans = 0
    for a, b, c in es:
        if dist[a][b] == c: continue
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import combinations
    import sys
    input = sys.stdin.readline

    inf = 1000 * 100 + 10

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

    dist = [[[inf, 0] for _ in range(N)] for _ in range(N)]
    for j in range(N):
        dist[j][j] = [0, 0]

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

    for k in range(N):
        for i in range(N):
            for j in range(N):
                nd = dist[i][k][0] + dist[k][j][0]
                if dist[i][j][0] > nd:
                    dist[i][j][0] = nd
                    dist[i][j][1] = dist[i][k][1] | dist[k][j][1]
                elif dist[i][j][0] == nd:
                    dist[i][j][1] |= dist[i][k][1] | dist[k][j][1]

    used_edge = 0
    for frm, to in combinations(range(N), r=2):
        used_edge |= dist[frm][to][1]

    print(M - bin(used_edge).count('1'))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000001)

def main():
    n, m = map(int, input().rstrip().split())
    dist = [[500000 for i in range(n)]for j in range(n)]

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

    a = [None] * m
    b = [None] * m
    c = [None] * m

    for i in range(m):
        x, y, z = map(int, input().rstrip().split())
        dist[x-1][y-1] =  min(dist[x-1][y-1], z)
        dist[y-1][x-1] =  min(dist[x-1][y-1], z)
        a[i] = x - 1
        b[i] = y - 1
        c[i] = z
        
    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])
    
    result = m

    for i in range(m):
        for j in range(n):
            if dist[j][a[i]] + c[i] == dist[j][b[i]]:
                result -= 1
                break

    print(result)
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000001)

def main():
    n, m = map(int, input().rstrip().split())
    dist = [[500000 for i in range(n)]for j in range(n)]

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

    a = []
    b = []
    c = []

    for i in range(m):
        x, y, z = map(int, input().rstrip().split())
        dist[x-1][y-1] =  min(dist[x-1][y-1], z)
        dist[y-1][x-1] =  min(dist[x-1][y-1], z)
        a.append(x-1)
        b.append(y-1)
        c.append(z)
        
    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])
    
    result = m

    for i in range(m):
        for j in range(n):
            if dist[j][a[i]] + c[i] == dist[j][b[i]]:
                result -= 1
                break

    print(result)
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000001)

n, m = map(int, input().rstrip().split())
dist = [[500000 for i in range(n)]for j in range(n)]

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

a = []
b = []
c = []

for i in range(m):
    x, y, z = map(int, input().rstrip().split())
    dist[x-1][y-1] =  min(dist[x-1][y-1], z)
    dist[y-1][x-1] =  min(dist[x-1][y-1], z)
    a.append(x-1)
    b.append(y-1)
    c.append(z)
    
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])

result = m

for i in range(m):
    for j in range(n):
        if dist[j][a[i]] + c[i] == dist[j][b[i]]:
            result -= 1
            break

print(result)

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

INF = 10**7
dist = [[INF for j in range(N)] for i in range(N)]
d = [[INF for j in range(N)] for i in range(N)]
prev = [[i for j in range(N)] for i in range(N)]
t = [[0 for j in range(N)] for i in range(N)]


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

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


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

warshall_floyd(N)
ans = 0
for i in range(N):
    for j in range(N):
        if dist[i][j] != INF and d[i][j] != dist[i][j]:
            ans += 1
print(ans//2)

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

INF = 10**7
dist = [[INF for j in range(N)] for i in range(N)]
d = [[INF for j in range(N)] for i in range(N)]
prev = [[i for j in range(N)] for i in range(N)]
t = [[0 for j in range(N)] for i in range(N)]

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




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

warshall_floyd(N)
ans = 0
for i in range(N):
    for j in range(N):
        if dist[i][j] != INF and d[i][j] != dist[i][j]:
            ans += 1
print(ans//2)