N, M = gets.split.map(&:to_i)
L = []
C = Hash.new(10_000_000)
M.times do
  a, b, c = gets.split.map(&:to_i)
  L.push [a, b, c]
  C[[a, b]] = C[[b, a]] = c
end

def smaller(a, b)
  a < b ? a : b 
end

dp = Array.new(N + 1) do |k|
  Hash.new do |h, x|
    i, j = x
    d = dp[k - 1]
    h[x] = smaller(d[x], d[[i, k]] + d[[k, j]])
  end
end

dp[0] = C

puts L.count{|a, b, c| dp[N][[a, b]] != C[[a, b]]}