{-# LANGUAGE FlexibleContexts #-}

import Data.Array
import Data.Array.ST
import Data.Bool
import qualified Data.ByteString.Char8 as C
import Data.List
import Control.Monad
import Control.Monad.ST
import qualified Data.Set as S

type Edge   = [Int]
type Weight = Int
type Vertex = Int
type Graph  = Array Vertex [(Vertex, Weight)] -- adjacent edge list

main = sol <$> get >>= print

get = fmap (unfoldr (C.readInt . C.dropWhile (==' '))) . tail . C.lines <$> C.getContents

sol es = S.size $ foldr upd edges vertices
  where
  g = buildGraph es
  edges = S.fromList $ fmap (\[u,v,_] -> (min u v,max u v)) es
  vertices = indices g
  paths g = fmap (\(u,v) -> (min u v,max u v)) . assocs . snd . dijkstra g
  upd v e = foldr S.delete e $ paths g v

buildGraph :: [Edge] -> Graph
buildGraph es = accumArray accm [] bnds udes
  where
  accm e a = bool (a:e) e (a `elem` e)
  udes = concatMap (\[u,v,c] -> [(u,(v,c)),(v,(u,c))]) es
  bnds = liftM2 (,) minimum maximum $ fst <$> udes

dijkstra :: Graph -> Vertex -> (Array Vertex Weight, Array Vertex Vertex)
dijkstra g v0 = runST $ do
  da <- newArray (bounds g) maxBound :: ST s (STUArray s Vertex Weight)
  writeArray da v0 0
  pa <- newArray (bounds g) ix :: ST s (STUArray s Vertex Vertex)
  let loop q = case S.minView q of
        Nothing -> return ()
        Just ((d,u),q') ->
          let f q (v,w) = do
                d0 <- readArray da v
                if d+w >= d0 then
                  return q
                else do
                  writeArray da v (d+w)
                  writeArray pa v u
                  return . S.insert (d+w,v) $ S.delete (d0,v) q
          in  foldM f q' (g!u) >>= loop
  loop $ S.singleton (0,v0)
  d <- freeze da
  p <- freeze pa
  return (d,p)

ix = 0 -- root sentinel

shortestPath :: Graph -> Vertex -> Vertex -> [Vertex]
shortestPath g fr to = go to [] 
  where
  pa = snd $ dijkstra g fr
  go v vs
    | v == ix   = vs
    | otherwise = go (pa!v) (v:vs)
 