import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)
import Data.List
import Data.Array.IO
import Control.Monad

main = do
  [n,m] <- map read . words <$> getLine :: IO [Int]
  edge <- (\[x,y,z] -> zip3 x y z) . transpose <$> getInt2DListBC
  graph <- newArray ((1, 1), (n, n)) (10^8) :: IO Memo2D
  road <- newArray ((1, 1), (n, n)) True :: IO Road
  foldM initWF graph edge
  let index = [(k, i, j) | k <- [1..n], i <- [1..n], j <- [1..n]]
  foldM (warshallFloyd road) graph index
  ans <- flip div 2 . length . filter (==True) <$> getElems road
  print $ m - ans

bsToInt :: BC.ByteString -> Int
bsToInt = fst . fromJust . BC.readInt

getInt2DListBC :: IO [[Int]]
getInt2DListBC = map (map bsToInt . BC.words) . BC.lines <$> BC.getContents

type Memo2D = IOUArray (Int, Int) Int
type Road = IOUArray (Int, Int) Bool

initWF :: Memo2D -> (Int, Int, Int) -> IO Memo2D
initWF memo (x, y, d) = do
  writeArray memo (x, y) d
  writeArray memo (y, x) d
  return memo

warshallFloyd :: Road -> Memo2D -> (Int, Int, Int) -> IO Memo2D
warshallFloyd road memo (k, i, j) = do
  let (ii, jj) = if i < j then (i, j) else (j, i)
  b <- readArray road (ii, jj)
  x <- readArray memo (ii, jj)
  y <- readArray memo (ii, k)
  z <- readArray memo (k, jj)
  let minWeight = min x $ y + z
  writeArray road (ii, jj) $ b && x < y + z
  writeArray memo (ii, jj) minWeight
  writeArray road (jj, ii) $ b && x < y + z
  writeArray memo (jj, ii) minWeight
  return memo
