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 dist = Array.make n None in
  let rec bfs01 d = function
    | [] -> ()
    | cvs ->
        List.map (fun (c, v) -> dfs c d [] v) cvs
        |> List.concat
        |> bfs01 (1 + d)
  and dfs c d acc v =
    if IntSet.mem c visited.(v) then acc
    else begin
      visited.(v) <- IntSet.add c visited.(v);
      (if dist.(v) = None then dist.(v) <- Some d);
      List.fold_left (fun acc (c', u) ->
        if c = c' then dfs c d acc u
        else (c', u) :: acc) acc es.(v)
    end in
  dist.(0) <- Some 0;
  bfs01 1 es.(0);
  match dist.(n - 1) with
  | None -> print_endline "-1"
  | Some d -> Printf.printf "%d\n" d

