#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<pli> vpli;
typedef vector<vi> mat;

inline ll read() {
    ll Hashimoto=0,Kanna=1;
    char I_Love=getchar();
    while(I_Love<'0'||I_Love>'9') {
        if(I_Love=='-')Kanna=-1;
        I_Love=getchar();
    }
    while(I_Love>='0'&&I_Love<='9') {
        Hashimoto=Hashimoto*10+I_Love-'0';
        I_Love=getchar();
    }
    return Hashimoto*Kanna;
}

template<typename T1,typename T2> inline void Umax(T1 &a,T2 b){
    if(a<b)a=b;
}
template<typename T1,typename T2> inline void Umin(T1 &a,T2 b){
    if(a>b)a=b;
}

#define I_Love_Hashimoto_Kanna main
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
#define file freopen("I_Love_Hashimoto_Kanna.out","w",stdout);
#define RE cout<<"I_Love_Hashimoto_Kanna"<<endl;
#define Tone(Kanna) cout<<Kanna<<endl;
#define Tall(Hashimoto,Kanna) for(int I_Love=0;I_Love<Kanna;I_Love++)cout<<Hashimoto[I_Love]<<(I_Love==Kanna-1?"\n":" ");
#define FOR(I_Love,Hashimoto,Kanna) for(int I_Love=Hashimoto;I_Love<Kanna;I_Love++)
#define MP(Hashimoto,Kanna) make_pair(Hashimoto,Kanna)
#define REV(Kanna) reverse(Kanna.begin(),Kanna.end());
#define SORT(Kanna) sort(Kanna.begin(),Kanna.end());
#define inf (int)1e9
#define linf (ll)1e18
#define mod (inf+7)

int n,m;
int MX=0;

vi vert[1111111];
vpii cp[1111111];
int num[1111111];

vi g[1111111];
int dp[1111111];

struct UnionFind {
    int f[1111111];
    int sz[1111111];
    void init(){
        FOR(i,0,1111111)f[i]=i,sz[i]=1;
    }
    int F(int x) {
        return (f[x]==x?x:f[x]=F(f[x]));
    }
    inline void M(int a,int b) {
        a=F(a);
        b=F(b);
        if(a==b)return ;
        if(sz[a]<sz[b]) {
            f[a]=b;
            sz[b]+=sz[a];
        } else {
            f[b]=a;
            sz[a]+=sz[b];
        }
    }
} uf;
queue<int>q;

void init(){
    uf.init();
    FOR(i,0,MX){
        vert[i].clear();
        cp[i].clear();
        g[i].clear();
    }

}

void solve(){
    init();
    MX=0;
    FOR(i,0,m) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        a--;b--;
        Umax(MX,c+1);
        cp[c].push_back({a,b});
        vert[c].push_back(a);
        vert[c].push_back(b);
    }
    int nn=n;
    FOR(c,0,MX) {
        if(cp[c].size()==0)continue;
        SORT(vert[c]);
        FOR(j,0,cp[c].size()) {
            uf.M(cp[c][j].first,cp[c][j].second);
        }
        FOR(j,0,vert[c].size()) {
            if(j)if(vert[c][j]==vert[c][j-1])continue;
            if(!num[uf.F(vert[c][j])]) {
                num[vert[c][j]]=num[uf.F(vert[c][j])]=nn++;
            } else num[vert[c][j]]=num[uf.F(vert[c][j])];
        }
        FOR(j,0,vert[c].size()) {
            if(j&&vert[c][j]==vert[c][j-1])continue;
            g[num[vert[c][j]]].push_back(vert[c][j]);
            g[vert[c][j]].push_back(num[vert[c][j]]);
            num[vert[c][j]]=0;
            uf.f[vert[c][j]]=vert[c][j];
            uf.sz[vert[c][j]]=1;
        }
    }
    FOR(i,0,nn) {
        dp[i]=-2;
    }
    Umax(MX,nn+1);
    dp[0]=0;
    q.push(0);
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        FOR(i,0,g[x].size()) {
            int to=g[x][i];
            if(dp[to]==-2) {
                dp[to]=dp[x]+1;
                q.push(to);
            }
        }
    }
    printf("%d\n",dp[n-1]/2);
}

int I_Love_Hashimoto_Kanna() {
    fastio;
    while(scanf("%d%d",&n,&m)!=EOF){
        solve();
    }
    return 0;
}

Measured memory_bytes: 113408