#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
typedef pair<ll,P> P1;
const ll mod=1e9+7;

struct edge{
  ll to,c;
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    vector<edge> g[100010];
    vector<ll> cnt;
    rep(i,m){
      ll p,q,c;
      cin>>p>>q>>c;
      g[p].push_back({q,c});
      g[q].push_back({p,c});
      if(p==1 || q==1) cnt.push_back(c);
    }
    ll dist[100010];
    ll inf=1e15;
    rep(i,100010) dist[i]=inf;
    dist[1]=0;
    priority_queue<P1> que;
    rep(i,len(cnt)) que.push(P1(0,P(1,cnt[i])));
    while(!que.empty()){
      P1 p=que.top();
      que.pop();
      ll d=p.first,v=p.second.first,c=p.second.second;
      if(dist[v]<d) continue;
      for(auto itr:g[v]){
        if(itr.c==c && dist[itr.to]>d){
          dist[itr.to]=d;
          que.push(P1(d,P(itr.to,itr.c)));
        }
        if(itr.c!=c && dist[itr.to]>d+1){
          dist[itr.to]=d+1;
          que.push(P1(d+1,P(itr.to,itr.c)));
        }
      }
    }
    if(dist[n]==inf) cout<<-1<<endl;
    else cout<<dist[n]+1<<endl;
}