exception Found of int

module IntSet = Set.Make (struct
  type t = int
  let compare = compare
end)

let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let es = Array.make n [] in
  for i = 0 to m - 1 do
    Scanf.scanf "%d %d %d\n" @@ fun p q c ->
      es.(p - 1) <- (c, q - 1) :: es.(p - 1);
      es.(q - 1) <- (c, p - 1) :: es.(q - 1)
  done;
  let visited = Array.make n IntSet.empty in
  let rec bfs01 d t = function
    | [] -> ()
    | cvs ->
        List.map (fun (c, v) -> dfs t c d [] v) cvs
        |> List.concat
        |> bfs01 (1 + d) t
  and dfs t c d acc v =
    if IntSet.mem c visited.(v) then acc
    else begin
      (if v = t then raise (Found d));
      visited.(v) <- IntSet.add c visited.(v);
      List.fold_left (fun acc (c', u) ->
        if c = c' then dfs t c d acc u
        else (c', u) :: acc) acc es.(v)
    end in
  try
    bfs01 1 (n - 1) es.(0);
    print_endline "-1"
  with Found d -> Printf.printf "%d\n" d
