#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAXN=(int)1e6+5;
const int MOD=(int)1e9+7;
namespace fastIO {
    #define BUF_SIZE 100000
    //fread -> read
    bool IOerror = 0;
    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if(p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if(pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }
    inline bool read(int &x) {
        char ch;
        while(blank(ch = nc()));
        if(IOerror)
            return false;
        for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
        return true;
    }
    #undef BUF_SIZE
};
using namespace fastIO;
int mark[MAXN],fa[MAXN];
vector<int>ed[MAXN];
vector<pii>ve[MAXN];
int fifa(int a){
    if(fa[a]!=a)fa[a]=fifa(fa[a]);
    return fa[a];
}
int dis[MAXN],vis[MAXN];
int zz[MAXN],f[MAXN];
int hh[MAXN];
int main()
{
    int n,m;
    while(read(n)){
        read(m);
        for(int i=1;i<=n;i++)ve[i].clear();
        for(int i=0;i<m;i++){
            int u,v,w;
            read(u);read(v);read(w);
            ve[u].push_back(mp(w,i));
            ve[v].push_back(mp(w,i));
            zz[w]=-1;
            if(u==1||v==1)hh[i]=1;
            else hh[i]=0;
            if(u==n||v==n)mark[i]=1;
            else mark[i]=0;
            fa[i]=i;
            ed[i].clear();
            vis[i]=0;
        }
        if(m==0){
            printf("-1\n");
            continue;
        }
        if(n==1){
            printf("1\n");
            continue;
        }
        for(int i=1;i<=n;i++){
            for(auto p:ve[i]){
                if(zz[p.fi]!=-1){
                    fa[fifa(p.se)]=zz[p.fi];
                }
                else {
                    int u=fifa(p.se);
                    zz[p.fi]=u;
                }
            }
            for(auto p:ve[i])zz[p.fi]=-1;
        }
        int ans=(int)1e9;
        int tot=m;
        for(int i=1;i<=n;i++){
            if(ve[i].empty())continue;
            ed[tot].clear();mark[tot]=0;
            vis[tot]=0;
            for(auto p:ve[i]){
                int u=fifa(p.se);
                if(f[u])continue;
                f[u]=1;
                ed[tot].push_back(u);
                ed[u].push_back(tot);
            }
            for(auto p:ve[i]){
                int u=fa[p.se];
                f[u]=0;
            }
            tot++;
        }
        for(int i=0;i<m;i++){
            if(mark[i])mark[fifa(i)]=1;
        }
        queue<int>q;
        for(int i=0;i<m;i++){
            int u=fifa(i);
            if(vis[u]||!hh[i])continue;
            q.push(u);
            vis[u]=1;
            dis[u]=2;
        }

        while(!q.empty()){
            int u=q.front();q.pop();
            if(mark[u]){
                ans=dis[u];
                break;
            }
            for(auto v:ed[u]){
                if(!vis[v]){
                    vis[v]=1;
                    dis[v]=dis[u]+1;
                    if(mark[v]){
                        ans=dis[v];
                        break;
                    }
                    q.push(v);
                }
            }
            if(ans!=(int)1e9)break;
        }
        if(ans==(int)1e9)printf("-1\n");
        else printf("%d\n",ans>>1);
      //  debug((double)clock()/CLOCKS_PER_SEC);
    }
    return 0;
}

Measured memory_bytes: 84608