#include <iostream>
#include <string>
using namespace std;
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200010
#define LIMIT2 500010
#define LIMIT3 1000010
#define INF ((1<<30)-1)
#define LLINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef long double ld;
typedef const void cv;
typedef pair<ll,ll> P;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define per(i,n) for((i)=(n)-1;(i)>=0;(i)--)
template<class T,class C> T max(T a,C b){ return ((a)>(T)(b) ? (a) : (T)(b)); }
template<class T,class C> T min(T a,C b){ return ((a)<(T)(b) ? (a) : (T)(b)); }
#define zt(a,b) (max((a),(b))-min((a),(b)))
#define setpre(n) fixed << setprecision(n)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
int upint(cv *a, cv *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(cv *a, cv *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
int upchar(cv *left, cv *right) {return strcmp((char *)left,(char *)right);}
int downchar(cv *left, cv *right) {return strcmp((char *)right,(char *)left);}
ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1){
      res *= a; if(mod>=1) res %= mod;
    }
    a *= a; if(mod>=1) a %= mod;
    n >>= 1;
  }
  return res;
}
void initialize(){
  
}
struct edge{
  int to,type;
};
typedef multimap<P,edge> trainSys;
multimap<P,edge> train;
vector<ll> types[LIMIT1];
map<P,ll> dist;
typedef pair<ll,pair<ll,ll> > PP;
ll getDist(ll stat,ll type){
  if(!dist.count(P(stat,type))) return LLINF;
  else return dist[P(stat,type)];
}
int main(void){
  initialize();
  ll n,m,i,j,k,result=0;
  int a[LIMIT2]={0};
  ll p,q,c;
  string s;
  priority_queue<PP,vector<PP>,greater<PP> > que;
  
  cin >> n >> m;
  rep(i,m){
    cin >> p >> q >> c;
    p--,q--,c--;
    edge es;
    es.type = c;
    es.to = q;
    train.insert(trainSys::value_type(make_pair(p,c),es));
    types[p].push_back(c);
    es.to = p;
    train.insert(trainSys::value_type(make_pair(q,c),es));
    types[q].push_back(c);
  }
  P start = make_pair(0,-1);
  dist[start]=0;
  que.push(make_pair(0,start));
  while(!que.empty()){
    auto p = que.top(); que.pop();
    auto posi = p.second;
    auto stat = posi.first;
    auto type = posi.second;
    if(p.first > getDist(stat,type)) continue;
    if(type==-1){
      //特定の会社の路線に入る
      ll cost=getDist(stat,type)+1;
      for(auto q : types[stat]){
        if(getDist(stat,q) > cost){
          que.push(make_pair(cost,make_pair(stat,q)));
          dist[make_pair(stat,q)] = cost;
        }
      }
    }else{
      //駅の移動
      ll cost=getDist(stat,type);
      auto mv = train.equal_range(make_pair(stat,type));
      for(auto it = mv.first;it!=mv.second;++it){
        auto q = it->second;
        if(q.type != type) continue;
        if(getDist(q.to,type) > cost){
          que.push(make_pair(cost,make_pair(q.to,type)));
          dist[make_pair(q.to,type)] = cost;
        }
      }
      //改札を出る
      if(getDist(stat,-1) > cost){
        que.push(make_pair(cost,make_pair(stat,-1)));
        dist[make_pair(stat,-1)] = cost;
      }
    }
  }
  rep(i,n){
    //cout << getDist(i,-1) << (i==n-1 ? '\n' : ' ');
  }
  result = (dist.count(make_pair(n-1,-1)) ? dist[make_pair(n-1,-1)] : -1);
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 75016