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