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-----
3 3
1 2 1
1 3 1
2 3 3

-----Sample Output-----
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.

Difficulty: interview

Starter code:

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

    

def dijkstra(s,cost):
  d = [float("inf")]*(n+1)
  used = [False]*(n+1)
  d[s] = 0
  
  while True:
    v = -1
    for i in range(1,n+1):
      if (not used[i]) and (v == -1):
        v = i
      elif (not used[i]) and d[i] < d[v]:
        v = i
    if v == -1:
      break
    used[v] = True
               
    for j in range(1,n+1):
      d[j] = min(d[j],d[v]+cost[v][j])
  return d

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

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

import numpy as np
Graph = np.array([[0 if i == j else np.inf for i in range(N)] for j in range(N)])
for a,b,c in Edge:
    Graph[a-1,b-1] = c
from scipy.sparse.csgraph import dijkstra 
Graph = dijkstra(Graph,directed=False)
ans = 0
for a,b,c in Edge:
    if Graph[a-1,b-1] != c:
        ans += 1
print(ans)

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

INF = float('inf')
ds = [[INF]*N for _ in range(N)]
for i in range(N):
    ds[i][i] = 0
for a,b,c in ABC:
    a,b = a-1,b-1
    ds[a][b] = ds[b][a] = c

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

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

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

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

cnt = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if(i == j):
                graph[i][j] = 0
                continue    
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

ans = M
for u, v, w in C:
    Flg = False
    for i in range(N):
        if(graph[i][v] + w == graph[i][u]):
            Flg = True
    if Flg:
        ans -= 1
print(ans)

N, M = list(map(int,input().split()))
E = set()
d = [[10**9]*N for k in range(N)]
for k in range(N):
    d[k][k] = 0
for k in range(M):
    a, b, c = list(map(int,input().split()))
    E.add((a-1,b-1,c))
    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):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
ans = 0
for e in E:
    if d[e[0]][e[1]] != e[2]:
        ans += 1
print(ans)


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

N,M=map(int,input().split())
G= [[0]*(N+1) for _ in range(N+1)]
abc = [list(map(int,input().split())) for _ in range(M)]

for a, b, c in abc:
  G[a][b] = c
  G[b][a] = c

cost = floyd_warshall(csr_matrix(G))
cnt = 0
for a, b, c in abc:
  if cost[a][b] < c:
    cnt += 1
print(cnt)

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)

import math
#import numpy as np
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 = list(map(int,ipt().split()))
    cos = []
    row = []
    col = []
    for _ in range(m):
        a,b,c = list(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

def __starting_point():
    main()

__starting_point()

import heapq


def dijkstra(n, s, g):
    h = [(0, s)]
    heapq.heapify(h)
    cost = [float("Inf")] * (n + 1)  # cost: i -> j
    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 = list(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))


def __starting_point():
    main()

__starting_point()

N,M = list(map(int,input().split()))
from collections import deque
v = [deque([]) for _ in range(N)]

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

s = deque([])
for i in range(N):
    ls = [[-1,M*10000]]*N
    ls[i] =  [-1,0]
    q = [deque(j for j in k) for k in v]
    l = deque([i])
    while l:
        u = l.popleft()
        x = len(q[u])
        for i in range(x):
            e = q[u].popleft()
            if ls[u][1] + e[1] < ls[e[0]][1]:
                ls[e[0]] = [u, ls[u][1] + e[1]]
                l.append(e[0])
            q[u].append(e)
    for j,e in enumerate(ls):
        if e[0] != -1:
             s.append([min(j,e[0]),max(j,e[0])])

s = list(map(list, set(map(tuple, s))))
print((M-len(s)))


N, M = list(map(int, input().split()))
d = [[1000000]*N for _ in range(N)]
d_dict = {}

inf = 0
for i in range(M):
  a, b, c = list(map(int, input().split()))
  d[a-1][b-1] = c
  d[b-1][a-1] = c
  d_dict[(a-1, b-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 = 0
for key in d_dict:
  if d[key[0]][key[1]] < d_dict[key]:
    ans += 1
    
print(ans)


#!/usr/bin/env python3
import sys

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    import numpy as np    
    from scipy.sparse import csr_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    omat = csr_matrix((c+c, (a+b, b+a)), shape=(N+1, N+1), dtype=np.int32)
    smat = floyd_warshall(omat)
    return ((omat-smat) > 0).sum() // 2


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    print((solve(N, M, a, b, c)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

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,w = map(int,input().split(" "))

a = []

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

for i in range(w):
    x,y,z = map(int,input().split(" "))
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    a.append([x,y,z])
for i in range(n):
    d[i][i] = 0

d = warshall_floyd(d)

ans = w
for i in range(len(a)):
    for s in range(n):
        if d[s][a[i][1]-1] + a[i][2] == d[s][a[i][0]-1]:
            ans -= 1
            break

print(ans)

N,M = list(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 = list(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

#　d[a][b]:aとbの距離
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))


# まずワーシャルフロイドの表を作る
# 元の表で頂点A-Bを結ぶ距離が、ワーシャルフロイドの表で短縮されていたら、その辺は使わないで良いことになる
# この個数を数える

import sys
readline = sys.stdin.readline

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense

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

INF = 10 ** 9
G = [[INF] * N for i in range(N)]
for i in range(M):
  a,b,c = map(int,readline().split())
  G[a-1][b-1] = c
  G[b-1][a-1] = c

d = csgraph_from_dense(G, null_value=10**9)
d = floyd_warshall(d)

ans = 0
for a in range(N-1):
  for b in range(a + 1,N):
    if G[a][b] == INF:
      continue
    if G[a][b] > d[a][b]:
      ans += 1
      
print(ans)

# https://atcoder.jp/contests/abc051/tasks/abc051_d
# 想定解法
# 最短距離の隣接行列Dが与えられたときに、edges[a, b]が最短経路に含まれるかどうか考える
# 2点s,tについて、最短距離であれば、D[s,t]=D[s,i]+edges[i,j]+D[j,t]を満たすi,jの組み合わせは最短経路辺である
# 5000*1000の探索なので間に合う

from scipy.sparse import csr_matrix  # 自分で配列を作ってからcsrに入れよう(lilに打ち込んでいくのは非常に遅い)

# ダイクストラ法 (正の単一始点最短経路) (全点間最短経路)
from scipy.sparse.csgraph import dijkstra
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


N, M = read_ints()
adj_mat = [[0] * N for _ in range(N)]
INF = 10 ** 9
from collections import defaultdict
from itertools import combinations
edges = defaultdict(lambda: INF)
for _ in range(M):
    a, b, c = read_ints()
    a -= 1
    b -= 1
    adj_mat[a][b] = c
    adj_mat[b][a] = c
    edges[a, b] = c

adj_mat = csr_matrix(adj_mat, dtype='int')
D = dijkstra(adj_mat, directed=False)
# print(D)

# 最短経路じゃない辺全探索
edge_not_use = set()
# 辺を固定してs,tを全探索したほうが良さそう
# だけどこれはTLE(pythonが遅いせい)
# for (i, j), e in edges.items():
#     for s, t in combinations(range(N), 2):
#         d = D[s, t]
#         if d == D[s, i] + e + D[j, t] or d == D[t, i] + e + D[j, s]:
#             break
#     else:
#         edge_not_use.add((i, j))

# よく考えてみれば
# D[s,j]=D[s,i]+edges[i,j]のedges[i,j]は最短経路の一部になっているはず(s→jの最短経路の一部を成す)
# sを全探索するだけでいい

for (i, j), e in list(edges.items()):
    for s in range(N):
        d = D[s, j]
        if d == D[s, i] + e or d == D[s, j] + e:
            break
    else:
        edge_not_use.add((i, j))


print((len(edge_not_use)))
# print(edge_not_use)


#!/usr/bin/env python3
import sys

def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    import numpy as np    
    from scipy.sparse import csr_matrix    
    from scipy.sparse.csgraph import floyd_warshall
    omat = csr_matrix((c, (a, b)), shape=(N+1, N+1), dtype=np.int32)
    smat = floyd_warshall(omat, directed=False)
    return ((smat-omat) < 0).sum()


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    print((solve(N, M, a, b, c)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

N,M=map(int,input().split())
graph=[[] for _ in range(N)]
cost=[[float("inf")]*N for _ in range(N)]
for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    cost[a-1][b-1]=c
    cost[b-1][a-1]=c

def dijkstra(S,N,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[S]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

dist=[]
for s in range(N):
    dist.append(dijkstra(s,N,cost))

checked=[[False]*N for _ in range(N)]
ans=M
for s in range(N):
    for i in range(s,N):
        for j in graph[i]:
            if checked[i][j]:
                continue
            
            if dist[s][i]+cost[i][j]==dist[s][j]:
                ans-=1
                checked[i][j]=True
                checked[j][i]=True
print(ans)

import heapq

def main():
    N, M = list(map(int, input().split()))
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b, c = list(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()))


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

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)

def dijkstra(s):
    import  heapq
    dist=[inf for i in range(n)] #sからの距離のリスト
    dist[s]=0
    mirai=[True for i in range(n)] #Trueなら未確定
    mirai[s]=False

    queue=[] #こいつがheapqになる
    for kyori,to in G[s]:
        heapq.heappush(queue , kyori*10**6+to)  #重みと行先を1つの変数で表してる！
    while queue:
        minedge= heapq.heappop(queue)
        #miraiがTrueのやつ(未確定なやつ)から最小距離のものをさがす
        if not mirai[minedge%(10**6)]: continue
        #距離が小さいものから"確定"していく
        v=minedge%(10**6) #最小距離の頂点
        dist[v] = minedge//(10**6) #その距離
        mirai[v]=False
        for kyori,to in G[v]:
            if mirai[to]:
                heapq.heappush(queue, (kyori+dist[v])*(10**6)+to)
                #queueに入る数は、必ず「sからの」距離と行先を持っている
    return dist
n,m=list(map(int,input().split()))
inf=10**10
G=[[] for i in range(n)]
HEN=[]
for i in range(m):
    a,b,c=list(map(int,input().split()))
    a-=1;b-=1
    G[a].append((c,b))
    G[b].append((c,a))
    HEN.append((a,b,c))

MIN=[[10**10]*n for i in range(n)]
for i in range(n):
    MIN[i]=dijkstra(i)
ans=0
for a,b,c in HEN:
    for s in range(n):
        if MIN[s][a]+c == MIN[s][b]:
            break
        if MIN[s][b]+c == MIN[s][a]:
            break
    else:
        ans+=1
print(ans)


# solution

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

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

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

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

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

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

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *ABC = list(map(int, read().split()))
    G = [[INF] * N for _ in range(N)]
    edge = [0] * M
    for i, (a, b, c) in enumerate(zip(*[iter(ABC)] * 3)):
        edge[i] = (a - 1, b - 1, c)
        G[a - 1][b - 1] = G[b - 1][a - 1] = c
    for i in range(N):
        G[i][i] = 0

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

    ans = 0
    for a, b, c in edge:
        if c > G[a][b]:
            ans += 1

    print(ans)
    return


def __starting_point():
    main()

__starting_point()

import heapq

def dijkstra(s):
    inf = 1145141919810
    dist = [inf] * v
    dist[s] = 0
    c = [0] * v
    p = []
    heapq.heapify(p)
    heapq.heappush(p, (dist[s], s))
    while p:
        d, u = heapq.heappop(p)
        if dist[u] < d:
            continue
        c[u] = 1
        for g in G[u]:
            if c[g[0]] == 0 and dist[u] + g[1] < dist[g[0]]:
                dist[g[0]] = dist[u] + g[1]
                heapq.heappush(p, (dist[g[0]], g[0]))
    return dist

n, m = map(int, input().split())
v = n
G = [[] for _ in range(v)]
E = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append([b, c])
    G[b].append([a, c])
    E.append([a, b, c])
mindist = [dijkstra(i) for i in range(v)]
ans = m
for e in E:
    for i in range(n):
        if mindist[i][e[0]] - mindist[i][e[1]] == e[2]:
            ans -= 1
            break
print(ans)

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

edge = set()
INF = float('inf')
cost = [[INF]*n for _ in range(n)]
for i in range(n):
    cost[i][i] = 0
for a, b, c in abc:
    a, b = a-1, b-1
    cost[a][b] = c
    cost[b][a] = c
    edge.add((a, b, c))

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

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

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

#ワーシャルフロイド法
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
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)

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

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

ans = M
for i in range(M):
  tmp = 0
  for j in range(N):
    if d[j][a[i]] + c[i] == d[j][b[i]]:
      tmp = 1
  ans -= tmp
print(ans)

import sys

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

memo = [[sys.maxsize]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
  memo[i][i] = 0

lst = []
for _ in range(M):
  a,b,c = map(int, input().split())
  memo[a][b] = c
  memo[b][a] = c
  lst.append((a,b,c))
  
for k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      memo[i][j] = min(memo[i][j], memo[i][k] + memo[k][j])
      
cnt = 0
for a,b,c in lst:
  if memo[a][b] < c:
    cnt += 1
    
print(cnt)

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
ma = [[0]*n for _ in range(n)]
list_ABC = [ list(map(int,input().split(" "))) for i in range(m)]
for a, b, c in list_ABC:
    ma[a-1][b-1] = c
    ma[b-1][a-1] = c

x = csr_matrix(ma)
y = dijkstra(x, directed=False).astype(int)

ans = 0

for a, b, c in list_ABC:
  if y[a-1][b-1] != c:
      ans += 1

print(ans)

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


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


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


resolve()


import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *ABC = list(map(int, read().split()))
    G = [[INF] * N for _ in range(N)]
    edge = [0] * M
    for i, (a, b, c) in enumerate(zip(*[iter(ABC)] * 3)):
        edge[i] = (a - 1, b - 1, c)
        G[a - 1][b - 1] = G[b - 1][a - 1] = c
    for i in range(N):
        G[i][i] = 0

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

    ans = 0
    for a, b, c in edge:
        used = False
        for i in range(N):
            if G[i][b] == G[i][a] + c or G[i][a] == G[i][b] + c:
                used = True
                break
        if not used:
            ans += 1

    print(ans)
    return


def __starting_point():
    main()

__starting_point()

N,M = map(int,input().split())
DP = [[float('inf')]*N for _ in range(N)]
B = []
for i in range(N):
  DP[i][i] = 0
for _ in range(M):
  a,b,c = map(int,input().split())
  DP[a-1][b-1] = c
  DP[b-1][a-1] = c
  B.append([a-1,b-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])   
ans = 0
for i in range(M):
    a,b,c = B[i]
    for j in range(N):
        if DP[j][b] == DP[j][a] + c:
            break
    else:
        ans += 1
print(ans)

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)

import sys


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


sys.setrecursionlimit(20000000)


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

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

    def warshall_floyd(d):
        # d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    if d[i][j] > d[i][k] + d[k][j]:
                        d[i][j] = d[i][k] + d[k][j]
                        if i < j:
                            if (i, j) in L:
                                S.append((i, j))
                        else:
                            if (j, i) in L:
                                S.append((j, i))
        return d

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


def __starting_point():
    main()

__starting_point()

import heapq


INF = float('inf')
N, M = list(map(int, input().split()))
to = [[] for _ in range(N)]
sides = [[0] * N for _ in range(N)]


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


def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) 
    cost = [[INF, []] for i in range(N)]
    cost[s][0] = 0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v][0]:
            continue
        for d, u in to[v]:
            tmp = d + cost[v][0]
            if tmp < cost[u][0]:
                cost[u][0] = tmp
                cost[u][1] = [v]
                heapq.heappush(hq, (tmp, u))                    
            elif tmp == cost[u][0]:
                cost[u][1].append(v)
                heapq.heappush(hq, (tmp, u))
    return cost


def dfs(v, tree, p=-1):
    if p >= 0:
        sides[v][p] = 0
        sides[p][v] = 0
    for nv in tree[v][1]:
        dfs(nv, tree, v)


def main():
    for s in range(N):
        tree = dijkstra(s)
        for g in range(N):
            dfs(g, tree)

    print((sum(sum(column) for column in sides) // 2))


def __starting_point():
    main()

__starting_point()

import heapq
import sys

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


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


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

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

    # ワーシャルフロイド
    for k in range(N):
        for i in range(N):
            for j in range(N):
                tmp = dp[i][k] + dp[k][j]
                if tmp < dp[i][j]:
                    dp[i][j] = tmp

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


def __starting_point():
    main()

__starting_point()

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
N, M, *ABC = [int(_) for _ in open(0).read().split()]
ABC = np.array(ABC)
F = floyd_warshall(
    csr_matrix((ABC[2::3], (ABC[::3], ABC[1::3])), (N + 1, N + 1)), 0)
print((np.sum(F[ABC[::3], ABC[1::3]] != ABC[2::3])))


def main():
    import sys
    # readline = sys.stdin.readline
    readlines = sys.stdin.readlines
    N, M = list(map(int, input().split()))
    edge = []
    dp = [[10 ** 9] * N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
    for s in readlines():
        a, b, c = list(map(int, s.split()))
        a -= 1; b -= 1
        edge.append((a, b, c))
        dp[a][b] = c
        dp[b][a] = c
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

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


def __starting_point():
    main()

__starting_point()

import copy
N, M = list(map(int, input().split()))

inf = 10 ** 9 + 7
dp = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    dp[a][b] = c
    dp[b][a] = c

old_dp = copy.deepcopy(dp)
check = [[False] * N for _ in range(N)]
count = 0
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])

count = 0
for i in range(N):
    for j in range(N):
        if old_dp[i][j] != dp[i][j] and old_dp[i][j] != inf:
            count += 1

print((count // 2))


# https://atcoder.jp/contests/abc051/submissions/1055446

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

    inf = 1000 * 100 + 10

    N, M = list(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 = list(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)


def __starting_point():
    main()

__starting_point()

n, m = map(int, input().split())
graph = [[float('inf')]*n for i in range(n)]
u_s=[]
v_s=[]
w_s=[]
for _ in range(m):
    u, v, w = map(int, input().split())
    u_s.append(u-1)
    v_s.append(v-1)
    w_s.append(w)
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0


def warshall_floyd(d):
    # d[i][j] : i から j への最短距離
    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

dist=warshall_floyd(graph)

ans=0
for i in range(m):
    if w_s[i]>dist[u_s[i]][v_s[i]]:
        ans+=1

print(ans)

from heapq import heappush,heappop
INF=10**20

def dijkstra(G, start = 0):
    d = [INF for i in range(len(G))]
    d[start] = 0
    prev = [0 for i in range(len(G))]
    
    que = []
    heappush(que, (0, start))

    while len(que) != 0:
        p = heappop(que)
        v = p[1]
        
        if d[v] < p[0]:
            continue
            
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                prev[u] = v
                heappush(que, (d[u], u))
    
    return d,prev

N,M=map(int,input().split())
G=[{} for _ in range(N+1)]

edgelist=[]
for i in range(M):
  a,b,c=map(int,input().split())
  G[a][b]=G[b][a]=c
  a,b=sorted([a,b])
  edgelist.append((a,b))
edgelist = set(edgelist)
  
shortest_edges=set()
for i in range(1,N+1):
  d,prev = dijkstra(G,i)
  for j in range(1,N+1):
    if j ==i:continue
    a,b = sorted([j,prev[j]])
    shortest_edges.add((a,b))
    
diff = edgelist.difference(shortest_edges)
print(len(diff))

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

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)


def __starting_point():
    main()
__starting_point()

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        i -= 1
        j -= 1
        tree[i].append((k, j))
        tree[j].append((k, i))

    # dijkstra
    import heapq
    from numpy import zeros

    ans = 0
    for i in range(n):
        for j in tree[i]:
            seen = zeros(n)
            goal = j[1]
            base = j[0]
            seen[i] = 1
            todo = []
            heapq.heapify(todo)
            for k in tree[i]:
                if k[0] < base and k != j:
                    heapq.heappush(todo, k)
            while len(todo) > 0:
                k = heapq.heappop(todo)
                if k[1] == goal:
                    if k[0] < base:
                        ans += 1
                    break
                seen[k[1]] = 1
                for l in tree[k[1]]:
                    if seen[l[1]] == 0 and k[0] + l[0] < base:
                        heapq.heappush(todo, (k[0] + l[0], l[1]))

    print(ans // 2)

main()

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    N, W = map(int, input().split())
    #初期化
    dp = [[inf]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] = 0
    abc = [list(map(int, input().split())) for _ in range(W)]
    for a,b,c in abc:
        dp[a-1][b-1] = c
        dp[b-1][a-1] = c

    #kを経由してiからjに行く行き方を考える
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dp[i][k]==inf or dp[k][j]==inf:
                    continue
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
    
    res = 0
    for a,b,c in abc:
        for k in range(N):
            if dp[a-1][k] == c + dp[b-1][k]:
                res += 1
                break
    print(W - res)

def __starting_point():
    main()
__starting_point()

import itertools
from scipy.sparse.csgraph import floyd_warshall

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

# Floyd-Warshallでよくやる初期化
dist = []
for i in range(N):
  tmp = []
  for _ in range(N):
    tmp.append(float('inf'))
  dist.append(tmp)
  dist[i][i] = 0  # ここがポイント

# 隣接行列を作る
a = []
b = []
c = []
for _ in range(M):
  x = list(map(int, input().split()))
  a.append(x[0] - 1)
  b.append(x[1] - 1)
  c.append(x[2])
  dist[a[-1]][b[-1]] = x[2]
  dist[b[-1]][a[-1]] = x[2]

# Floyd-Warshall
dist = floyd_warshall(dist)
dist = dist.astype(int).tolist()

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

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
edges = [(i - 1, j - 1, c) for i, j, c in edges]

INF = int(10000)

dp = [[INF for _ in range(N)] for _ in range(N)]
for i, j, cost in edges:
    dp[i][j] = cost
    dp[j][i] = cost

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

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

count = 0
for i, j, cost in edges:
    if dp[i][j] < cost:
        count += 1

print(count)

def main():
    n, m, *abc = list(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)


def __starting_point():
    main()

__starting_point()

# https://atcoder.jp/contests/abc051/submissions/1055446

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

    inf = 1000 * 100 + 10

    N, M = list(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 = list(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)


def __starting_point():
    main()

__starting_point()

n,m = map(int,input().split())
INF = float("inf")
g = [[INF]*n for _ in range(n)]
e = []
for i in range(m):
    vi,vj,w = map(int,input().split())
    g[vi-1][vj-1] = w
    g[vj-1][vi-1] = w
    e.append((vi-1,vj-1,w))

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
cnt = 0
for x,y,z in e:
    if g[x][y] < z:
        cnt += 1
print(cnt)

import networkx as nx
import itertools

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

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

N, M = (int(x) for x in input().split())
graph = [[1000] * N for _ in range(N)]
before = []
for _ in range(M):
    a,b,c = (int(x) for x in input().split())
    before.append((a-1,b-1,c))
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

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

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

ans = 0
for x in before:
    if graph[x[0]][x[1]] != x[2]:
        ans += 1
print(ans)

import networkx as nx
import itertools

N, M = list(map(int, input().split()))
G = nx.Graph()
G.add_nodes_from(list(range(1, N + 1)))
G.add_weighted_edges_from([list(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)


def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
              #if (d[i][k] != float("INF")) and (d[k][j] != float("INF")):
                d[i][j] = min(d[i][k] + d[k][j], d[i][j])
                
        #print(d)
    return d

##############################
n,m = list(map(int,input().split())) #n:頂点数　m:辺の数

d = [[float("INF")] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)

hen = [0] * m
for i in range(m):
    x,y,z = list(map(int,input().split()))
    d[x - 1][y - 1] = z
    d[y - 1][x - 1] = z
    hen[i] = [x - 1, y - 1, z]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

ans = warshall_floyd(d)
#それぞれの出発地点ごとにmaxをとり、そのmaxが最小の地点に引っ越し
#そのときの所要時間がp
#print(used)
answer = 0
for i in range(m):
  now = hen[i]
  if d[now[0]][now[1]] != now[2]:
    answer += 1
  
print(answer)  



from collections import defaultdict
import heapq


INF = 10 ** 6


def check(N, adj_nodes, costs, from_node, to_node):
    # calculate shortest distances on a graph without a edge (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)


def __starting_point():
    main()

__starting_point()

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

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

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

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

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

from scipy.sparse.csgraph import floyd_warshall

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

edge = [[float("inf") for i in range(N)] for j in range(N) ]

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

dist = floyd_warshall(edge)

ans = 0

for a,b,c in abc:
    if dist[a-1][b-1] != c:
        ans += 1

print(ans)

from scipy.sparse.csgraph import *
import numpy as np
N,M = map(int,input().split())
E = [list(map(int,input().split())) for m in range(M)]
G = np.zeros((N,N))
ans = 0

for a,b,c in E:
  G[a-1][b-1] = c
  G[b-1][a-1] = c

F = shortest_path(G).astype(int)
for a,b,c in E:
  if F[a-1][b-1]!=c:
    ans+=1

print(ans)

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

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

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

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

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

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

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

INF = float("inf")

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


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

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

D = WarshallFloyd(E)

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

#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    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])
    return wf #d[i][j]に頂点i, j間の最短距離を格納

##############################

n, m = list(map(int,input().split())) #N:頂点数 m:辺の数
d = [[INF] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
edges = []
for i in range(m):
    u, v, w = list(map(int,input().split()))
    d[u-1][v-1] = w
    d[v-1][u-1] = w
    edges.append((u-1,v-1))
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

fwd = warshall_floyd(d)   #d[i][j]に頂点i, j間の最短距離を格納

ret = 0
for u,v in edges:
    if fwd[u][v] < d[u][v]:
        ret += 1
print(ret)


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


N,M = map(int,input().split())
f = lambda x: (int(x[0])-1,int(x[1])-1,int(x[2]))
edges = list(f(input().split()) for _ in range(M))

g = np.zeros((N,N), dtype=float)

for a,b,c in edges:
    g[a,b] = c
    g[b,a] = c

floyd_warshall(g, directed=False, overwrite=True)

res = sum(int(g[a,b] != c) for a,b,c in edges)
print(res)

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

G = [[] for _ in range(N)]
INF = 10**9
D = [[ INF for _ in range(N)] for _ in range(N)]
for i in range(N):
  D[i][i] = 0

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

for k in range(N):
  for i in range(N):
    for j in range(N):
      if D[i][k] + D[k][j] < D[i][j]:
        D[i][j] = D[i][k] + D[k][j]
        D[j][i] = D[i][k] + D[k][j]
  
ans = 0
for a,b,c in E:
  flg = False
  for i in range(N):
    if D[i][a] + c == D[i][b]:
      flg = True
      break
   
  if not flg:
    ans += 1
    
print(ans)

import heapq
n, m = map( int, input().split() )
adj_list = [ [] for i in range( n+1 ) ]
for _ in range( m ):
    a, b, c = map( int, input().split() )
    adj_list[ a ].append( ( b, c ) )
    adj_list[ b ].append( ( a, c ) )

# dijkstra
def dijkstra( start ):
    prev_node = [ -1 ] * ( n + 1 )
    INF = 10 ** 10
    VISITED = 1
    NOT_VISITED = 0
    cost = [ INF ] * ( n + 1 )
    cost[ start ] = 0
    visit = [ NOT_VISITED ] * ( n + 1 )
    queue = [ ( cost[ start ], start ) ]
    while len( queue ) > 0:
        c, v = heapq.heappop( queue )
        visit[ v ] = VISITED
        for u, cost_vu in adj_list[v]:
            if visit[ u ] == VISITED:
                continue
            if cost[u] > cost[v] + cost_vu:
                cost[u] = cost[v] + cost_vu
                heapq.heappush( queue, ( cost[u], u ) )
                prev_node[ u ] = v
    return prev_node

used_edge = [ [ False ] * ( n+1 ) for i in range( n+1 ) ]

used_count = 0
for s in range( 1, n+1 ):
    prev_node = dijkstra( s )
    for i in range( 1, n+1 ):
        j = prev_node[ i ]
        if j == -1:
            continue
        if used_edge[ i ][ j ] == False:
            used_count += 1
            used_edge[ i ][ j ] = True
            used_edge[ j ][ i ] = True

print( m - used_count )

import heapq


INF = float('inf')
N, M = map(int, input().split())
to = [[] for _ in range(N)]

#sides[i][j] : i-->jへ向かう辺を通るかどうかを保持
# 1 : 通る、0 : 通らない
sides = [[0] * N for _ in range(N)]


for _ in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    to[a].append((c, b))
    to[b].append((c, a))
    sides[a][b] = 1 #a, b間に辺がある
    sides[b][a] = 1


# dijkstraで最短経路木をつくる
def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) 
    cost = [[INF, []] for i in range(N)]
    cost[s][0] = 0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v][0]:
            continue
        for d, u in to[v]:
            tmp = d + cost[v][0]
            if tmp < cost[u][0]:
                cost[u][0] = tmp
                cost[u][1] = [v] # 更新する場合は直前の頂点を保持
                heapq.heappush(hq, (tmp, u))
            elif tmp == cost[u][0]:
                cost[u][1].append(v) # 距離が等しい場合はリストで直前の頂点を保持  
                heapq.heappush(hq, (tmp, u))
    return cost


# 作成した最短経路木を探索して、通る辺を調べる
def dfs(v, tree, p=-1):
    if p >= 0:
        sides[v][p] = 0
        sides[p][v] = 0
    for nv in tree[v][1]:
        dfs(nv, tree, v)


def main():
    for s in range(N):
        tree = dijkstra(s)
        for g in range(N):
            dfs(g, tree)

    print(sum(sum(column) for column in sides) // 2)


def __starting_point():
    main()
__starting_point()

#051_D
inf = 10 ** 10
n, m = map(int, input().split())
d = [[inf for _ in range(n)] for _ in range(n)]
for i in range(n):
    d[i][i] = 0
edges = []
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
    edges.append((a-1, b-1, c))

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])
                
warshall_floyd(d)

ans = m
for u, v, c in edges:
    flg = False
    for i in range(n):
        if d[i][v] + c == d[i][u]:
            flg = True
    
    if flg:
        ans -= 1

print(ans)

n,w = map(int,input().split()) #n:頂点数　w:辺の数
from collections import defaultdict
D=defaultdict(list)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j]>d[i][k]+d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    D[(i,j)]=D[(i,k)]+D[(k,j)][1:]
    return d
done=[[-1]*n for _ in range(n)]
d = [[float("inf")]*n for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    D[(x-1,y-1)]=[x-1,y-1]
    D[(y-1,x-1)]=[y-1,x-1]
    done[x-1][y-1]=0
    done[y-1][x-1]=0
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)
for l in D.values():
    for i in range(1,len(l)):
        a=l[i-1]
        b=l[i]
        done[a][b]=1
        done[b][a]=1
import numpy as np
done=np.array(done)
ans=(done==0).sum()
#print(D)
#print(done)
print(ans//2)

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)

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
 
n, m = map(int, input().split())
ma = [[0]*n for _ in range(n)]
list_ABC = [ list(map(int,input().split(" "))) for i in range(m)]

for a, b, c in list_ABC:
  ma[a-1][b-1] = c
  ma[b-1][a-1] = c
  
y = dijkstra(ma, directed=False).astype(int)
 
ans = 0
 
for a, b, c in list_ABC:
  if y[a-1][b-1] != c:
    ans += 1
    
print(ans)

n,m= map(int,input().split())
rg = [[999999999 for _ in range(n)] for _ in range(n)]
rgflg = [[False for _ in range(n)] for _ in range(n)]
for i in range(m):
    a,b,c= map(int,input().split())
    rg[a-1][b-1] = c
    rgflg[a-1][b-1] = True
    rg[b-1][a-1] = c
    rgflg[b-1][a-1] = True
count=0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if rg[i][j] > rg[i][k] + rg[k][j]:
                rg[i][j] = rg[i][k] + rg[k][j]
                if rgflg[i][j]==True or rgflg[j][i]==True:
                    rgflg[i][j]=False
                    rgflg[j][i]=False
                    count+=1
print(count)

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

    inf = 1000 * 100 + 10

    N, M = list(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 = list(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  # weight,edge_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(list(range(N)), r=2):
        used_edge |= dist[frm][to][1]

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


def __starting_point():
    main()

__starting_point()

import heapq
n, m = list(map(int, input().split()))
edges = dict()
ans = [0 for _ in range(m + 1)]
graph = [set() for _ in range(n)]


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

# (cost,done,node,edge)
for i in range(n):
    done = [True for _ in range(n)]
    D = [(0, 0, i, m), ]
    heapq.heapify(D)

    while D:
        d = heapq.heappop(D)
        cost, mark, node, edge = d

        if done[node]:
            done[node] = False
            ans[edge] = 1

            for g in graph[node]:
                a, b, c = edges[g]

                if b == node:
                    a, b = b, a

                if done[b]:
                    heapq.heappush(D, (cost + c, ans[g], b, g))

print((m - (sum(ans) - 1)))


import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, m = list(map(int, input().split()))
d = [[INF for j in range(n)] for i in range(n)]
x = []
for i in range(m):
    a, b, c = list(map(int, input().split()))
    x.append([a - 1, b - 1, c])
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c
d2 = warshall_floyd(d, n)
# print(d2)
ans = 0
for i in x:
    if d2[i[0]][i[1]] != i[2]:
        ans += 1
print(ans)


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)

n, m = map(int, input().split())
INF = 10**10
d = [[INF]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
nxt = [[[i] for i in range(n)] for _ in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            if d[i][k]+d[k][j] < d[i][j]:
                d[i][j] = d[i][k]+d[k][j]
                nxt[i][j] = nxt[i][k][:]
            elif d[i][k]+d[k][j] == d[i][j]:
                nxt[i][j] += nxt[i][k]
s = set()
for start in range(n):
    for goal in range(n):
        if start==goal:
            continue
        def DFS(i):
            for j in nxt[i][goal]:
                s.add((i, j))
                if j!=goal:
                    DFS(j)
        DFS(start)
print(m-len(s)//2)

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

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

d=[[float("inf")]*N for i in range(N)]
A=[]
for i in range(M):
  x,y,z=map(int, input().split())
  x-=1
  y-=1
  d[x][y]=z
  d[y][x]=z
  A.append((x,y,z))
  
for i in range(N):
  d[i][i]=0 
  
D=warshall_floyd(d)

ans=0
for x,y,z in A:
  if D[x][y]!=z:
    ans+=1
print(ans)

import sys
import heapq
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def dijkstra_heap(s):
        d = [f_inf] * n
        used = [True] * n
        d[s] = 0
        used[s] = False
        edgelist = []
        for e in edge[s]:
            heapq.heappush(edgelist, e)
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            if not used[minedge[1]]:
                continue
            v = minedge[1]
            d[v] = minedge[0]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heapq.heappush(edgelist, [e[0] + d[v], e[1]])
        return d

    used = set()
    for i in range(n):
        dist = dijkstra_heap(i)
        for d, to, fr in k:
            if dist[to] + d == dist[fr]:
                used.add((to, fr))

    print((len(k) - len(used)))

def __starting_point():
    resolve()

__starting_point()

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

INF = float('inf')
ds = [[INF]*N for _ in range(N)]
for i in range(N):
    ds[i][i] = 0
for a,b,c in ABC:
    a,b = a-1,b-1
    ds[a][b] = ds[b][a] = c

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

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

n, m = map(int, input().split())
dis = [[float("inf") for i in range(n)] for j in range(n)]
for i in range(n):
    dis[i][i] = 0
abc = []
for i in range(m):
    a, b, c = map(int, input().split())
    abc.append([a, b, c])
    dis[a-1][b-1] = c
    dis[b-1][a-1] = c
def warshall_floyd(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis1 = dis[i][j]
                dis2 = dis[i][k] + dis[k][j]
                dis[i][j] = min(dis1, dis2)
    return dis
data = warshall_floyd(dis)
ans = 0
for i in range(m):
    a, b, c = abc[i][0], abc[i][1], abc[i][2]
    for j in range(n):
        if c + data[b-1][j] == data[a-1][j]:
            break
    else:
        ans += 1
print(ans)

n,m=map(int,input().split())
class WarshallFloyd:
#O(V^3)で任意２頂点の最短距離
    def __init__(self,n,_first_index=0):
        self.v = n
        self._first_idx=_first_index
        self.d = [[1e100]*(n+_first_index) for _ in range(n+_first_index)]
        for i in range(n+_first_index):
            self.d[i][i] = 0

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

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

n, m = map(int, input().split())
Graph = [[float("inf")] * n for i in range(n)]
A, B, C = [], [], []
for i in range(n):
    Graph[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    Graph[a - 1][b - 1] = c
    Graph[b - 1][a - 1] = c
    A.append(a - 1)
    B.append(b - 1)
    C.append(c)
for k in range(n):
    for i in range(n):
        for j in range(n):
            Graph[i][j] = min(Graph[i][j], Graph[i][k] + Graph[k][j])
ans = m
for i in range(m):
    for j in range(n):
        if Graph[j][A[i]] + C[i] == Graph[j][B[i]]:
            ans -= 1
            break
print(ans)

import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = list(map(int, read().split()))
    G = [[] for _ in range(N)]
    for i, (a, b, c) in enumerate(zip(*[iter(AB)] * 3)):
        G[a - 1].append((b - 1, c, i))
        G[b - 1].append((a - 1, c, i))

    vec = [False] * M
    for i in range(N):
        dist = [INF] * N
        dist[i] = 0
        from_edge = [[] for _ in range(N)]
        hq = [(0, i)]

        while hq:
            d, v = heappop(hq)
            if dist[v] < d:
                continue
            for nv, cost, edge in G[v]:
                if dist[nv] > d + cost:
                    dist[nv] = d + cost
                    heappush(hq, (dist[nv], nv))
                    from_edge[nv] = [edge]
                elif dist[nv] == d + cost:
                    from_edge[nv].append(edge)

        for edges in from_edge:
            for e in edges:
                vec[e] = True

    ans = sum(1 for flag in vec if not flag)
    print(ans)
    return


def __starting_point():
    main()

__starting_point()

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

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

edges = []

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

for i in range(n):
    d[i][i] = 0
# print("d",d)

csr = csr_matrix(d)
dp = floyd_warshall(csr)
ans = 0
# print("dp",dp)

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

n,m=map(int,input().split())
INF=10**18
e=[[INF for _ in range(n)]for _ in range(n)]
d=[]
for i in range(m):
  a,b,c=map(int,input().split())
  e[a-1][b-1]=c
  e[b-1][a-1]=c
  d.append((a-1,b-1,c))
for k in range(n):
  for i in range(n):
    for j in range(n):
      e[i][j]=min(e[i][j],e[i][k]+e[k][j])
ans=0
for i,j,k in d:
  if e[i][j]!=k:ans+=1
print(ans)

INF=100000000
N,M=map(int,input().split())
a=[0]*1000
b=[0]*1000
c=[0]*1000
dist=[[INF for _ in range(100)] for _ in range(100)]
for i in range(M):
  a[i],b[i],c[i]=map(int,input().split())
  a[i]-=1
  b[i]-=1
for i in range(N):
  for j in range(N):
    if i==j:
      dist[i][j]=0
for i in range(M):
  dist[a[i]][b[i]]=min(dist[a[i]][b[i]],c[i])
  dist[b[i]][a[i]]=min(dist[b[i]][a[i]],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=M
for i in range(M):
  flag=False
  for j in range(N):
    if dist[j][a[i]]+c[i]==dist[j][b[i]]: flag=True
  if flag: ans-=1
print(ans)

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

d = [[inf]*N for i in range(N)]
prev = [[N]*N for i in range(N)]
vlist = [[0]*N for i in range(N)]

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

#####
#print("d",d)
#print("vlist",vlist)
#print("prev",prev)
#####

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

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

#####
#print("d",d)
#print("vlist",vlist)
#print("prev",prev)
#####

count = 0
for i in range(N-1):
    for j in range(i,N):
        if vlist[i][j] == 1 and vlist[j][i] == 1:
            count += 1

print(count)

N, M = list(map(int, input().split()))
conns = [tuple(map(int, input().split())) for _ in range(M)]
cost = [[float("INF")]*N for _ in range(N)]

# make same node cost zeros
for i in range(N):
  cost[i][i] = 0

# update edge cost
for a,b,c in conns:
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c

# find minimum cost across all pairs of nodes
for k in range(N):
  for i in range(N):
    for j in range(N):
      cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

# find edges without shortest path
cnt = 0
for a,b,c in conns:
  if c > cost[a-1][b-1]:
    cnt += 1

print(cnt)
  


import heapq


def dijkstra(n, s, g):
    h = [(0, s)]
    heapq.heapify(h)
    cost = [float("Inf")] * (n + 1)  # cost: i -> j
    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 = list(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)


def __starting_point():
    main()

__starting_point()

import heapq


def dijkstra(s):
    dist[s] = 0
    que = []
    heapq.heappush(que, (0, s))
    while len(que) != 0:
        p = heapq.heappop(que)
        v = p[1]
        if (dist[v] < p[0]):
            continue
        for e in graph[v]:
            if dist[e[0]] > dist[v] + e[1]:
                dist[e[0]] = dist[v] + e[1]
                prev[e[0]] = v
                heapq.heappush(que, (dist[e[0]], e[0]))


def get_path(t):
    path = []
    while t != -1:
        path.append(t)
        t = prev[t]
    path = path[::-1]
    return path


N, W = list(map(int, input().split()))
graph = [[] for i in range(N)]
edges = {}
for i in range(W):
    x, y, z = list(map(int, input().split()))
    x -= 1
    y -= 1
    graph[x].append((y, z))
    graph[y].append((x, z))
    edges[(x, y)] = True

for st in range(N):
    dist = [float("inf")] * N
    prev = [-1] * N
    dijkstra(st)
    for i in range(N):
        gp = get_path(i)
        for i in range(1, len(gp)):
            edges[(gp[i-1], gp[i])] = False

print((sum(edges.values())))


import sys
input = sys.stdin.readline

def main():
  n, m = map(int, input().split())
  road = [[100000]*n for _ in range(n)]
  count = [[-1]*n for i in range(n)]
  for _ in range(m):
    a, b, c = map(int, input().split())
    road[a-1][b-1] = c
    road[b-1][a-1] = c
    count[a-1][b-1] = 0
    count[b-1][a-1] = 0
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if road[i][k]+road[k][j] < road[i][j]:
          if count[i][j] == 0:
            count[i][j] = 1
          road[i][j] = road[i][k]+road[k][j]
  ans = 0
  for i in range(n):
    ans += count[i].count(1)
  print(ans//2)
def __starting_point():
  main()
__starting_point()

n, m = map(int, input().split())
graph = [[float('inf')]*n for i in range(n)]
u_s=[]
v_s=[]
w_s=[]
for _ in range(m):
    u, v, w = map(int, input().split())
    u_s.append(u-1)
    v_s.append(v-1)
    w_s.append(w)
    graph[u-1][v-1] = w
    graph[v-1][u-1] = w
for i in range(n):
    graph[i][i] = 0


def warshall_floyd(adj_m):
    # _dist[i][j] : i から j への最短距離
    _dist=adj_m
    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

dist=warshall_floyd(graph)

ans=0
for i in range(m):
    if w_s[i]>dist[u_s[i]][v_s[i]]:
        ans+=1

print(ans)

from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
def main():
    N, M = list(map(int, input().split()))
    w = [[0] * N for i in range(N)]
    l = []
    for i in range(M):
        a, b, c = list(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()))


# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

g = [[0 for _ in range(N)] for _ in range(N)]

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

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
csg = csgraph_from_dense(g)
d = floyd_warshall(csg, directed=False)

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

print(ans)

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = list(map(int, input().split()))
    cost = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        cost[i][i] = 0

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

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

    res = 0
    for d, x, y in edge:
        if cost[x][y] < d:
            res += 1
    print(res)


def __starting_point():
    resolve()

__starting_point()