#include <bits/stdc++.h>
using namespace std;

#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

constexpr int mod = 1e9 + 7;
constexpr int32_t inf = 1001001001;
constexpr int64_t infll = 1001001001001001001ll;
constexpr int dx[] = {0, -1, 1, 0, -1, 1, -1, 1}, dy[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const string YES = "YES", NO = "NO", Yes = "Yes", No = "No", yes = "yes", no = "no";

// clang-format off
// ostream &operator<<(ostream &os, __int128_t value) { if (ostream::sentry(os)) { __uint128_t tmp = value < 0 ? -value : value; char buffer[64]; char *d = end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); }} return os; }
// istream &operator>>(istream &is, __int128_t &value) { string in; is >> in; value = 0; for (const char &c : in) { if ('0' <= c && c <= '9') value = 10 * value + (c - '0'); } if (in[0] == '-') value *= -1; return is; }
// ostream &operator<<(ostream &os, __uint128_t value) { if (ostream::sentry(os)) { char buffer[64]; char *d = end(buffer); do { --d; *d = "0123456789"[value % 10]; value /= 10; } while (value != 0); int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); }} return os; }
// istream &operator>>(istream &is, __uint128_t &value) { string in; is >> in; value = 0; for (const char &c : in) { if ('0' <= c && c <= '9') value = 10 * value + (c - '0'); } return is; }
template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { os << v[0]; for (int i = 1; i < v.size(); ++i) os << " " << v[i]; return os; }
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.fs << " " << p.sc; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.fs >> p.sc; return is; }

struct IoSetup { IoSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup;

inline int64_t in() { int64_t x = 0; cin >> x; return x; }

template <typename T> void sort(vector<T> &v) { sort(all(v)); }
template <typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// clang-format on

template <typename T> struct Dijkstra {
  Dijkstra(size_t size) : size(size), G(size) {}

  struct edge {
    edge(int to, T cost) : to(to), cost(cost) {}
    int to;
    T cost;
  };

  using P = pair<T, int>;
  const T inf = numeric_limits<T>::max();

  size_t size;
  vector<vector<edge>> G;
  vector<T> d;

  void add_edge(int u, int v, T c) {
    // cerr << u << " -(" << c << ")> " << v << endl;
    G[u].push_back(edge(v, c));
  }

  void build(int s) {
    d.assign(size, inf);
    priority_queue<P, vector<P>, greater<P>> q;

    d[s] = 0;
    q.push(P(0, s));

    while (!q.empty()) {
      P p = q.top();
      q.pop();
      int v = p.second;
      if (d[v] < p.first) continue;
      for (auto &e : G[v])
        if (d[e.to] > p.first + e.cost) {
          d[e.to] = p.first + e.cost;
          q.push(P(d[e.to], e.to));
        }
    }
  }

  T operator[](int v) {
    return d[v];
  }
};

signed main(int argc, char *argv[]) {
  int n = in(), m = in();

  Dijkstra<int> G(n + 3 * m);
  map<int, int> ushi[101010];
  int idx = n;
  for (int i = 0; i < m; ++i) {
    int p = in() - 1, q = in() - 1, c = in();
    if (!ushi[p].count(c)) ushi[p][c] = idx++;
    if (!ushi[q].count(c)) ushi[q][c] = idx++;

    G.add_edge(p, ushi[p][c], 1);
    G.add_edge(ushi[p][c], p, 0);
    G.add_edge(q, ushi[q][c], 1);
    G.add_edge(ushi[q][c], q, 0);
    G.add_edge(ushi[p][c], ushi[q][c], 0);
    G.add_edge(ushi[q][c], ushi[p][c], 0);
  }

  G.build(0);
  cout << (G[n - 1] == G.inf ? -1 : G[n - 1]) << endl;
}


Measured memory_bytes: 63092