let inf, n, m, g, us = Scanf.scanf "%d %d" @@ fun n m -> Array.(100000000, n, m, make n [], make_matrix n n 0)
let h u v d = g.(u) <- (v, d) :: g.(u); g.(v) <- (u, d) :: g.(v); us.(u).(v) <- 1; us.(v).(u) <- 1
let f s ds ps = let q = ref [] in ds.(s) <- 0; for i = 0 to n - 1 do q := i :: !q done;
  while !q <> [] do let mi = ref (max_int, -1) in List.(iter (fun i -> mi := min !mi (ds.(i), i)) !q;
  let u = snd !mi in q := filter (fun i -> i <> u) !q; iter (fun (v, d) -> if ds.(v) > ds.(u) + d then (ds.(v) <- ds.(u) + d; ps.(v) <- [u]) else if ds.(v) = ds.(u) + d then ps.(v) <- u :: ps.(v)) g.(u)) done; Array.iteri (fun v -> List.iter (fun u -> us.(u).(v) <- 0)) ps
let _ = for _ = 1 to m do Scanf.scanf " %d %d %d" @@ fun u v d -> h (u - 1) (v - 1) d done; Array.(for i = 0 to n - 1 do f i (make n inf) (make n []) done; Printf.printf "%d\n" @@ fold_left (fold_left (+)) 0 us / 2)