#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <deque>
#include <stack>
#include <iomanip>
#include <cmath>


using namespace std;


typedef long long ll;
typedef long double ld;


const ll MOD = 1000000007ll;


ll modSum(ll a, ll b) {
  return ((a % MOD) + (b % MOD)) % MOD;
}


ll modProd(ll a, ll b) {
  return ((a % MOD) * (b % MOD)) % MOD;
}


ll getPowMod(ll x, ll e) {
  if (e == 0) return 1;
  if (e % 2 == 0) {
    ll tmp = getPowMod(x, e/2);
    return modProd(tmp, tmp);
  } else {
    ll tmp = getPowMod(x, e-1);
    return modProd(tmp, x);
  }
}


ll getPow(ll x, ll e) {
  if (e == 0) return 1;
  if (e % 2 == 0) {
    ll tmp = getPow(x, e/2);
    return tmp * tmp;
  } else {
    ll tmp = getPow(x, e-1);
    return tmp * x;
  }
}


bool isEven(ll x) {
  ll tmp = ((x % 2) + 2) % 2;
  return tmp == 0;
}


ll getSumOfDigitsInBase(ll n, ll b) {
  ll ret = 0;
  while (n > 0) {
    ret += n % b;
    n /= b;
  }
  return ret;
}


vector<int> getKMP(string &s) {
  int len = (int)s.size();
  vector<int> ret (len, 0);
  for (int i = 1 ; i < len ; i++) {
    int at = ret[i-1];
    while (at > 0 && s[i] != s[at]) {
      at = ret[at-1];
    }
    if (s[i] == s[at]) {
      at++;
    }
    ret[i] = at;
  }
  return ret;
}


string getSubstring(string &s, int from, int to) {
  int l = to-from+1;
  if (l <= 0) {
    return "";
  }
  return s.substr(from, l);
}













const int MAXN = 100001;


int N, M;
map<int, int> interesting, nxt_interesting;
set<int> uninteresting;
set<int> colors[MAXN];
set< pair<int, int> > explored;
map<int, set<int> > G[MAXN];


void DFS(int at, int c) {
  explored.insert({at, c});
  if (uninteresting.find(at) == uninteresting.end()) {
    if(nxt_interesting.find(at) == nxt_interesting.end()) {
      nxt_interesting[at] = (int)colors[at].size()-1;
    } else {
      nxt_interesting[at]--;
    }
    if (nxt_interesting[at] == 0) {
      nxt_interesting.erase(at);
      uninteresting.insert(at);
    }
  }
  for (auto nxt : G[at][c]) {
    if (explored.find({nxt, c}) == explored.end()) {
      DFS(nxt, c);
    }
  }
}


void input() {
  cin >> N >> M;
  int u, v, c;
  for (int i = 1 ; i <= M ; i++) {
    cin >> u >> v >> c;
    G[u][c].insert(v);
    G[v][c].insert(u);
    colors[u].insert(c);
    colors[v].insert(c);
  }
}


void preprocess() {
}


void solve() {
  interesting.insert({1, colors[1].size()});
  int depth = 0;
  while(!interesting.empty()) {
    cerr << "Depth = " << depth << "\n";
    if (uninteresting.find(N) != uninteresting.end() || interesting.find(N) != interesting.end()) {
      cout << depth;
      return;
    }
    depth++;
    for (auto pp : interesting) {
      int at = pp.first;
      cerr << "At = " << at << "\n";
      for (auto &p : G[at]) {
        int c = p.first;
        for (auto nxt : p.second) {
          cerr << "Nxt = " << nxt << "\n";
          if (explored.find({nxt, c}) == explored.end()) {
            DFS(nxt, c);
          }
        }
      }
    }
    interesting = nxt_interesting;
    nxt_interesting.clear();
  }
  if (uninteresting.find(N) != uninteresting.end()) {
    cout << depth;
  } else {
    cout << "-1";
  }
}


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

  int T;
//  cin >> T;
  T = 1;

  for (int i = 0 ; i < T ; i++) {
    input();
    preprocess();
    solve();
  }

  return 0;
}


Measured memory_bytes: 105088