
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 dijkstra :
    (* 隣接リスト *)
    (Vertex.t -> (Vertex.t * Weight.t) list) ->
    (* 始点 *)
    Vertex.t ->
    (* 始点から辿り着けなければNoneを返す *)
    (Vertex.t -> Weight.t option)
end =
struct
  module WMap = Map.Make (Weight)
  module VMap = Map.Make (Vertex)

  let dijkstra e s =
    (* 始点sからの距離 *)
    (* d に入っていない頂点への距離は無限大とみなす *)
    let d = ref @@ VMap.singleton s Weight.zero in
    (* 優先度付きキュー *)
    let q = ref @@ WMap.singleton Weight.zero [s] in
    (* ダイクストラ法のメインループ *)
    let rec dijkstra_aux t =
      match WMap.min_binding !q with
      | exception Not_found ->
          (try Some (VMap.find t !d) with Not_found -> None)
      | (w, us) ->
          if
            (* 現時点で終点までの距離が分かっているか *)
            try Weight.compare (VMap.find t !d) w <= 0
            with Not_found -> false
          (* 既に終点までの距離が分かっているので返す *)
          then Some (VMap.find t !d)
          else begin
            (* 終点までの距離が分かっていないので，ダイクストラ法を続行 *)
            q := WMap.remove w !q;
            List.iter (fun u ->
              if 0 <= Weight.compare (VMap.find u !d) w then
                (* 未だ頂点uを訪れていない *)
                List.iter (fun (v, c) ->
                  let open Weight in
                  if
                    try 0 < Weight.compare (VMap.find v !d) (w + c)
                    with Not_found -> true  (* d.(v) は無限大 *)
                  then begin
                    d := VMap.add v (w + c) !d;
                    q := WMap.add (w + c) (v :: try WMap.find (w + c) !q with Not_found -> []) !q
                  end) (e u)) us;
            dijkstra_aux t
          end in dijkstra_aux
end

module G = WeightedDirectedGraph
  (struct
    type t = int * int
    let compare = compare
  end)
  (struct
    type t = int
    let zero = 0
    let ( + ) = ( + )
    let compare = compare
  end)

module IntMap = Map.Make (struct
  type t = int
  let compare = compare
end)

let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let es = Array.make n IntMap.empty in
  for i = 0 to m - 1 do
    Scanf.scanf "%d %d %d\n" @@ fun p q c ->
      es.(p - 1) <- IntMap.add c (q - 1 :: try IntMap.find c es.(p - 1) with Not_found -> []) es.(p - 1);
      es.(q - 1) <- IntMap.add c (p - 1 :: try IntMap.find c es.(q - 1) with Not_found -> []) es.(q - 1)
  done;
  match
    G.dijkstra (function
      | (v, 0) -> List.map (fun (c, _) -> ((v, c), 1)) @@ IntMap.bindings es.(v)
      | (v, c) -> ((v, 0), 0) :: (List.map (fun v -> ((v, c), 0)) (try IntMap.find c es.(v) with Not_found -> []))) (0, 0) (n - 1, 0)
  with 
  | None -> print_endline "-1"
  | Some d -> Printf.printf "%d\n" d
