#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath> 
#include<cstring> 
#include<cassert>
#include<string>
#include<sstream>
#include<fstream>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<list>
#include<stack>
#include<set>
#include<bitset>
#include<iomanip>
#include<utility>
#include<functional>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cwchar>
#include<cwctype>
#include<exception>
#include<locale>
#include<numeric>
#include<new>
#include<stdexcept>
#include<limits>
#pragma GCC optimize(3)
using namespace std;

#define ll long long
#define INF 1e9
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pii pair<int,int>
#define sz(s) s.size()
#define all(s) (s.begin(),s.end())
inline void Fail(){
    printf("0");
    exit(0);
}

const int maxn=1000005;
int n,m,cnt,ln;
pair < int , pii > ve[maxn],tmpe[maxn];
vector<pii>edge[maxn];
vector<int>Nedge[maxn],all[maxn],path;
int p[maxn],ini[maxn],dist[maxn],sum[maxn];
bool vis[maxn],has[maxn];

void qread(int &x){
    int neg=1;x=0;
    char c=getchar(); 
    while(c<'0'||c>'9'){if(c=='-')neg=-1;c=getchar();}
    while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
    x*=neg;
}

void radix_sort_p3i_SC(pair < int , pii > *p,int len){
    int m=len;
    int mx=0;
    rep(i,m)sum[p[i].se.fi]++,mx=max(mx,p[i].se.fi);
    REP(i,mx)sum[i]+=sum[i-1];
    for(int i=m-1;i>=0;i--)tmpe[--sum[p[i].se.fi]]=p[i];
    memset(sum,0,sizeof(int)*(mx+2));
    memcpy(p,tmpe,sizeof(pair < int , pii >)*(len+1));
}

void bfs(int v,int color){
    path.clear();
    queue<int>q;
    q.push(v);
    vis[v]=true;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        path.push_back(x);
        for(int &i=p[x];i<edge[x].size();i++){
            pii y=edge[x][i];
            if(y.first!=color)break;
            if(!vis[y.second]){
                q.push(y.second);
                vis[y.second]=true;
            }
        }
    }
    rep(i,path.size())vis[path[i]]=false;
}

int main(){
    while(scanf("%d%d",&n,&m)==2){
        ln=0;
        rep(i,m){
            int a,b,c;
            qread(a);qread(b);qread(c);
            a--;b--;
            ve[ln++]=make_pair(a,make_pair(c,b));
            ve[ln++]=make_pair(b,make_pair(c,a));
            all[c].push_back(a);
            all[c].push_back(b);
            has[c]=1;
        }
        radix_sort_p3i_SC(ve,ln);
        int I;
        for(I=0;I<ln;++I){
            edge[ve[I].first].push_back(ve[I].second);
        }
        cnt=n;
        REP(i,1000000){
            if(!has[i]) continue;
            rep(j,all[i].size()){
                int x=all[i][j];
                if(ini[x]==i)continue;
                bfs(x,i);
                rep(k,path.size()){
                    int y=path[k];
                    ini[y]=i;
                    Nedge[cnt].push_back(y);
                    Nedge[y].push_back(cnt);
                }
                cnt++;
            }
            all[i].clear();
            has[i]=0;
        }
        rep(i,cnt)dist[i]=-2;
        dist[0]=0;
        queue<int>q;
        q.push(0);
        while(!q.empty()){
            int x=q.front();
            q.pop();
            rep(i,Nedge[x].size()){
                int y=Nedge[x][i];
                if(dist[y]==-2){
                    dist[y]=dist[x]+1;
                    q.push(y);
                }
            }
        }
        printf("%d\n",dist[n-1]/2);
        rep(i,n)edge[i].clear(),ini[i]=0,vis[i]=false,p[i]=0;
        rep(i,cnt)Nedge[i].clear();
    }
    return 0;
}

Measured memory_bytes: 117376