(* 座標圧縮 *)
module CoordComp
  (* 座標の型 *)
  (Coord : sig
    type t
    val compare : t -> t -> int
  end) :
sig
  val compress :
    (* 座標のリスト *)
    Coord.t list ->
    (* 座標の数，圧縮する関数と解凍する関数を返す *)
    int * (Coord.t -> int) * (int -> Coord.t)
end = struct
  module IntMap = Map.Make (struct
    type t = int
    let compare = compare
  end)
  module CoordMap = Map.Make (Coord)

  let compress cs =
    let (n, comp, decomp) =
      List.fold_left (fun (n, comp, decomp) c ->
        if CoordMap.mem c comp then (n, comp, decomp)
        else (n + 1, CoordMap.add c n comp, IntMap.add n c decomp))
      (0, CoordMap.empty, IntMap.empty) cs in
    (n, (fun c -> CoordMap.find c comp), (fun n -> IntMap.find n decomp))
end

(* 無限大の要素を付け足してトロピカル半環を作る *)
module WithInf
  (S : sig
    type t
    val zero : t
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  (* Noneで無限大を表す *)
  type t = S.t option
  val inf : t
  val zero : t
  val ( + ) : t -> t -> t
  val compare : t -> t -> int
end =
struct
  type t = S.t option
  let inf = None
  let zero = Some S.zero
  let ( + ) x y =
    match x, y with
    | None, _ -> None
    | _, None -> None
    | Some m, Some n -> Some (S.( + ) m n)
  let compare x y =
    match x, y with
    | None, None -> 0
    | None, _ -> 1
    | _, None -> -1
    | Some m, Some n -> S.compare m n
end

module WeightedDirectedGraph
  (Vertex : sig
    type t
    val compare : t -> t -> int
  end)
  (Weight : sig
    type t
    val zero : t
    val ( + ) : t -> t -> t
    val compare : t -> t -> int
  end) :
sig
  (* 配列版の実装 *)
  val raw_warshall_floyd :
    (* 頂点の数n *)
    int ->
    (* 辺のリスト *)
    (* 頂点は0からn-1までの整数でなくてはならない *)
    (int * int * Weight.t) list ->
    (* 辿り着けなければNoneを返す *)
    (int -> int -> Weight.t option)

  (* 座標圧縮により，頂点に様々な型を使えるようにしたバージョン *)
  val warshall_floyd :
    (* 辺のリスト *)
    (Vertex.t * Vertex.t * Weight.t) list ->
    (* 辿り着けなければNoneを返す *)
    (Vertex.t -> Vertex.t -> Weight.t option)
end =
struct
  module CC = CoordComp (Vertex)
  module Weight' = WithInf (Weight)

  let raw_warshall_floyd n es =
    (* 準備 *)
    (* Noneで無限を表す *)
    let d = Array.make_matrix n n Weight'.inf in
    List.iter (fun (u, v, c) -> d.(u).(v) <- Some c) es;
    for v = 0 to n - 1 do
      d.(v).(v) <- Weight'.zero
    done;
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
        for k = 0 to n - 1 do
          let open Weight' in
          (* d.(j).(i) + d.(i).(k) < d.(j).(k) *)
          if 0 < compare d.(j).(k) (d.(j).(i) + d.(i).(k)) then
            d.(j).(k) <- d.(j).(i) + d.(i).(k)
        done
      done
    done;
    fun u v -> try d.(u).(v) with _ -> Weight'.inf

  let warshall_floyd es =
    let (n, comp, _) =
      CC.compress @@
        List.concat @@
          List.map (fun (u, v, _) -> [u; v]) es in
    let d =
      raw_warshall_floyd n @@
        List.map (fun (u, v, c) -> (comp u, comp v, c)) es in
    fun u v ->
      try d (comp u) (comp v) with Not_found -> None
end

module Int = struct
  type t = int
  let zero = 0
  let ( + ) = ( + )
  let compare = compare
end

module G = WeightedDirectedGraph (Int) (Int)

let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let abcs =
    Array.to_list @@
      Array.init m @@ fun _ ->
        Scanf.scanf "%d %d %d\n" @@ fun a b c -> a, b, c in
  let d = G.warshall_floyd (List.map (fun (a, b, c) -> (b, a, c)) abcs @ abcs) in
  List.filter (fun (a, b, c) -> let Some d = d a b in d < c) abcs
  |> List.length
  |> Printf.printf "%d\n"

Measured memory_bytes: 5248