#include  <functional>
#include  <algorithm>
#include  <exception>
#include  <stdexcept>
#include  <streambuf>
#include  <iterator>
#include  <string.h>
#include  <stdlib.h>
#include  <typeinfo>
#include  <valarray>
#include  <iostream>
#include  <sstream>
#include  <istream>
#include  <stdio.h>
#include  <climits>
#include  <clocale>
#include  <complex>
#include  <csignal>
#include  <cstdarg>
#include  <cstddef>
#include  <ctype.h>
#include  <cassert>
#include  <cstdlib>
#include  <utility>
#include  <cstring>
#include  <numeric>
#include  <ostream>
#include  <cwctype>
#include  <fstream>
#include  <iomanip>
#include  <math.h>
#include  <bitset>
#include  <cctype>
#include  <string>
#include  <vector>
#include  <limits>
#include  <memory>
#include  <cerrno>
#include  <time.h>
#include  <iosfwd>
#include  <cfloat>
#include  <cstdio>
#include  <cwchar>
#include  <cmath>
#include  <ctime>
#include  <deque>
#include  <queue>
#include  <stack>
#include  <ios>
#include  <map>
#include  <set>
#include  <new>
#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxm=1000;
char buffer[maxm],*S,*T;
inline char Get_Char()
{
    if(S==T)
    {
        T=(S=buffer)+fread(buffer,1,maxm,stdin);
        if(S==T) return EOF;
    }
    return *S++;
}

int read()
{
    char c;
    int re=0;
    for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
    while(c>='0'&&c<='9')
           re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    return re;
}
const int maxn=100005;
int par[25][maxn],vis[25][maxn],hei[25][maxn],id[25][maxn],q[25][2*maxn];
int n,m,cols,sz,ans[25][maxn],p;
vector<pii> col[25][maxn];
vector<int> gra[25][maxn];
int findfa(int x)
{
    if(x==par[p][x])
    return x;
    else
    return par[p][x]=findfa(par[p][x]);
}
void unio(int x,int y)
{
    int fx=findfa(x),fy=findfa(y);
    if(fx==fy)
    return;
    if(hei[p][fx]<hei[p][fy])
    par[p][fx]=fy;
    else
    {
        par[p][fy]=fx;
        if(hei[p][fx]==hei[p][fy])
        hei[p][fx]++;
    }
}
inline void init(int i,int j)
{
    par[p][i]=i;
    par[p][j]=j;
    hei[p][i]=hei[p][j]=0;
    id[p][i]=id[p][j]=-1;
    vis[p][i]=vis[p][j]=0;
}
inline void clea(int i)
{
    for(int j=0;j<col[p][i].size();j++)
    init(col[p][i][j].first,col[p][i][j].second);
    for(int j=0;j<col[p][i].size();j++)
    unio(col[p][i][j].first,col[p][i][j].second);
}
inline void built(int i,int j)
{
    gra[p][i].pb(j);
    gra[p][j].pb(i);
}
int main()
{
    for(int i=0;i<25;i++)
    {
        for(int j=0;j<maxn;j++)
        ans[i][j]=-1;
    }
    while(~scanf("%d%d",&n,&m))
    {
        p++;
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        x=read();y=read();c=read();
        x--;y--;c--;
        cols=max(cols,c);
        col[p][c].pb(mp(x,y));
    }
    sz=n;
    for(int i=0;i<=cols;i++)
    {
        if(col[p][i].empty())
        continue;
        clea(i);
        for(int j=0;j<col[p][i].size();j++)
        {
            pii pi=col[p][i][j];
            if(!vis[p][pi.first])
            {
                vis[p][pi.first]=1;
                int fa=findfa(pi.first);
                if(id[p][fa]==-1)
                id[p][fa]=sz++;
                built(pi.first,id[p][fa]);
            }
            if(!vis[p][pi.second])
            {
                vis[p][pi.second]=1;
                int fa=findfa(pi.second);
                if(id[p][fa]==-1)
                id[p][fa]=sz++;
                built(pi.second,id[p][fa]);
            }
        }
    }
    int fron=0,tai=1;
    ans[p][0]=0;
    while(fron<tai)
    {
        int u=q[p][fron];
        fron++;
        for(int i=0;i<gra[p][u].size();i++)
        {
            int v=gra[p][u][i];
            if(ans[p][v]==-1)
            {
                ans[p][v]=ans[p][u]+1;
                q[p][tai]=v;
                tai++;
            }
        }
    }
    if(ans[p][n-1]<0)
    cout<<-1<<endl;
    else
    cout<<ans[p][n-1]/2<<endl;}
    return 0;
}

Measured memory_bytes: 153088