#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <type_traits>
#include <limits>
#include <tuple>
#include <map>
#include <queue>

template <typename WeightType>
class weighted_edge {
public:
  using size_type = size_t;
  using weight_type = WeightType;

protected:
  size_type M_src, M_dst;
  weight_type M_weight;

public:
  weighted_edge() = default;
  weighted_edge(weighted_edge const&) = default;
  weighted_edge(weighted_edge&&) = default;

  weighted_edge(size_type s, size_type d, weight_type w):
    M_src(s), M_dst(d), M_weight(w)
  {}

  weighted_edge& operator =(weighted_edge const&) = default;
  weighted_edge& operator =(weighted_edge&&) = default;

  bool operator <(weighted_edge const& other) const {
    if (M_weight < other.M_weight) return true;
    if (other.M_weight < M_weight) return false;
    if (M_src != other.M_src) return M_src < other.M_src;
    return M_dst < other.M_dst;
  }

  size_type source() const { return M_src; }
  size_type target() const { return M_dst; }
  weight_type weight() const { return M_weight; }
};

struct directed_tag {};
struct undirected_tag {};

template <typename Edge, typename Directedness>
class adjacency_list {
public:
  using size_type = size_t;
  using edge_type = Edge;
  using weight_type = typename Edge::weight_type;
  static weight_type const inf = std::numeric_limits<weight_type>::max();

private:
  std::vector<std::vector<edge_type>> M_g;

public:
  adjacency_list() = default;
  adjacency_list(adjacency_list const&) = default;
  adjacency_list(adjacency_list&&) = default;
  adjacency_list(size_type n): M_g(n) {}

  template <typename... Args>
  void emplace(size_type src, size_type dst, Args... args) {
    M_g[src].emplace_back(src, dst, args...);
    if (std::is_same<Directedness, undirected_tag>::value)
      M_g[dst].emplace_back(dst, src, args...);
  }

  size_type size() const { return M_g.size(); }
  std::vector<edge_type> const& operator [](size_type i) const { return M_g[i]; }
};

struct dijkstra_tag {} dijkstra;

template <typename Edge, typename Directedness>
auto shortest(adjacency_list<Edge, Directedness> const& g, size_t s, dijkstra_tag) {
  using weight_type = typename Edge::weight_type;
  using pair_type = std::pair<weight_type, size_t>;
  size_t n = g.size();
  std::vector<weight_type> dp(n, std::numeric_limits<weight_type>::max());
  dp[s] = weight_type(0);
  std::priority_queue<pair_type, std::vector<pair_type>, std::greater<>> pq;
  pq.emplace(weight_type(0), s);
  while (!pq.empty()) {
    weight_type w;
    size_t v;
    std::tie(w, v) = pq.top();
    pq.pop();
    if (dp[v] < w) continue;
    for (auto const& e: g[v]) {
      weight_type nw = dp[e.source()] + e.weight();
      size_t nv = e.target();
      if (nw < dp[nv]) {
        dp[nv] = nw;
        pq.emplace(std::move(nw), nv);
      }
    }
  }
  return dp;
}

template <typename Key, typename Compare = std::less<>>
class monotone_minimal_perfect_hash {
public:
  using size_type = size_t;

private:
  mutable std::map<Key, size_type, Compare> M_hf;
  mutable bool M_ready = false;

public:
  monotone_minimal_perfect_hash() = default;
  monotone_minimal_perfect_hash(monotone_minimal_perfect_hash const&) = default;
  monotone_minimal_perfect_hash(monotone_minimal_perfect_hash&&) = default;
  monotone_minimal_perfect_hash& operator =(monotone_minimal_perfect_hash const&) = default;
  monotone_minimal_perfect_hash& operator =(monotone_minimal_perfect_hash&&) = default;

  void push(Key const& k) {
    M_hf[k];
    M_ready = false;
  }
  size_type operator [](Key const& k) const {
    if (!M_ready) {
      size_t i = 0;
      for (auto& p: M_hf) p.second = i++;
      M_ready = true;
    }
    return M_hf.find(k)->second;
  }
  size_type size() const noexcept { return M_hf.size(); }

  auto begin() const { return M_hf.begin(); }
  auto end() const { return M_hf.end(); }
};

int main() {
  size_t n, m;
  scanf("%zu %zu", &n, &m);

  monotone_minimal_perfect_hash<std::pair<size_t, size_t>> mmph;
  for (size_t i = 1; i <= n; ++i) mmph.push({i, 0});

  std::vector<std::tuple<size_t, size_t, size_t>> es(m);
  for (auto& t: es) {
    size_t p, q, c;
    scanf("%zu %zu %zu", &p, &q, &c);
    mmph.push({p, c});
    mmph.push({q, c});
    t = std::make_tuple(p, q, c);
  }

  adjacency_list<weighted_edge<int>, directed_tag> g(mmph.size());
  for (auto& t: es) {
    size_t p, q, c;
    std::tie(p, q, c) = t;

    g.emplace(mmph[{p, c}], mmph[{q, c}], 0);
    g.emplace(mmph[{q, c}], mmph[{p, c}], 0);

    g.emplace(mmph[{p, c}], mmph[{p, 0}], 0);
    g.emplace(mmph[{q, c}], mmph[{q, 0}], 0);

    g.emplace(mmph[{p, 0}], mmph[{p, c}], 1);
    g.emplace(mmph[{q, 0}], mmph[{q, c}], 1);
  }

  size_t source = mmph[{1, 0}];
  size_t target = mmph[{n, 0}];

  int res = shortest(g, source, dijkstra)[target];
  if (res == g.inf) res = -1;
  printf("%d\n", res);
}


Measured memory_bytes: 94896