#include <bits/stdc++.h>

using namespace std;
using int64 = long long;
using IntPair = pair<int, int>;

constexpr int DEBUG = 0;

// Binary weight edge.
struct BWEdge {
  int from;
  int to;
  bool w;
  BWEdge(int from, int to, bool w) : from(from), to(to), w(w) {}
};

struct PairHash {
  std::size_t operator()(const pair<int, int>& k) const {
    return hash<int>()(k.first) * 1000000007 ^ hash<int>()(k.second);
  }
};

template<class T> inline bool UpdateMin(T& a, T b) {
  if (a > b) { a = b; return 1; } return 0;
}

template<class T> inline bool UpdateMax(T& a, T b) {
  if (a < b) { a = b; return 1; } return 0;
}

// Does coordinate compression of unordered elements.
// Templage arguments:
// - T: Type of values to compress.
// - H: Hash for the type T.
// Arguments:
// - raw_xs: Values to compress.
// Returns:
// - xs: Compressed values.
// - to:index: A mapping from a row value to a compressed value.
// - to_raw: A mapping from a compressed value to a raw value.
template<typename T, typename H>
tuple<vector<int>, unordered_map<T, int, H>, vector<T>> UnorderedCompress(const vector<T>& raw_xs) {
  unordered_set<T, H> raw_x_set(raw_xs.begin(), raw_xs.end());
  vector<T> to_raw(raw_x_set.begin(), raw_x_set.end());
  unordered_map<T, int, H> to_index;
  for (int i = 0; i < to_raw.size(); i++) {
    to_index[to_raw[i]] = i;
  }
  vector<int> xs;
  for (const T& raw_x : raw_xs) {
    xs.push_back(to_index[raw_x]);
  }
  return make_tuple(xs, to_index, to_raw);
}

vector<int> ZeroOneBFS(const vector<vector<BWEdge>>& graph, int s) {
  int n = graph.size();
  vector<int> ds(n, INT_MAX);
  vector<int> visited(n);
  deque<int> q;
  ds[s] = 0;
  q.push_back(s);

  while (!q.empty()) {
    int v = q.front();
    q.pop_front();

    if (visited[v]) continue;
    visited[v] = true;
    
    for (const auto& e : graph[v]) {
      int nv = e.to;
      int nd = ds[v] + (e.w ? 1 : 0);
      if (nd < ds[nv]) {
        ds[nv] = nd;
        if (e.w) {
          q.push_back(nv);
        } else {
          q.push_front(nv);
        }
      }
    }
  }
  return ds;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, m;
  cin >> n >> m;

  vector<int> v1s(m);
  vector<int> v2s(m);
  vector<int> cs(m);
  for (int i = 0; i < m; i++) {
    cin >> v1s[i] >> v2s[i] >> cs[i];
    v1s[i]--;
    v2s[i]--;
  }

  vector<IntPair> ps;
  for (int i = 0; i < n; i++) {
    ps.push_back(IntPair(i, 0));
  }
  for (int i = 0; i < m; i++) {
    IntPair p1 = IntPair(v1s[i], cs[i]);
    IntPair p2 = IntPair(v2s[i], cs[i]);
    ps.push_back(p1);
    ps.push_back(p2);
  }

  unordered_map<IntPair, int, PairHash> id_map;
  tie(ignore, id_map, ignore) = UnorderedCompress<IntPair, PairHash>(ps);
  int s = id_map.size();

  vector<vector<BWEdge>> graph(s);
  for (int i = 0; i < m; i++) {
    int v1 = v1s[i];
    int v2 = v2s[i];
    int c = cs[i];
    int a1 = id_map[IntPair(v1, 0)];
    int b1 = id_map[IntPair(v1, c)];
    int a2 = id_map[IntPair(v2, 0)];
    int b2 = id_map[IntPair(v2, c)];
    graph[a1].push_back(BWEdge(a1, b1, true));
    graph[b1].push_back(BWEdge(b1, a1, false));
    graph[a2].push_back(BWEdge(a2, b2, true));
    graph[b2].push_back(BWEdge(b2, a2, false));
    graph[b1].push_back(BWEdge(b1, b2, false));
    graph[b2].push_back(BWEdge(b2, b1, false));
  }

  auto ds = ZeroOneBFS(graph, id_map[IntPair(0, 0)]);

  int ans = INT_MAX;
  for (const auto& kv : id_map) {
    const auto& k = kv.first;
    if (k.first == n - 1) {
      UpdateMin(ans, ds[kv.second]);
    }
  }

  if (ans == INT_MAX) ans = -1;

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 93036