#include <algorithm>
#include <iterator>
#include <iostream>
//#include <iomanip>
//#include <cstring>
//#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
//#include <cmath>
//#include <set>
#include <map>
using namespace std;
const int MAXC = 1234567 ;

#define union _union_1337
#define ITRF itr->first
#define ITRS itr->second

typedef long long i64;

struct disjointSet
{
    int fa[MAXC];
    int son[MAXC];

    void clear(int N)
    {
        for(int i = 0; i <= N; i++)
            fa[i] = i;
    }

    int find(int x)
    {
        if(fa[x] == x)
            return x;
        return fa[x] = find(fa[x]);
    }

    void union(int x, int y)
    {
        int X = find(x), Y = find(y);
        if(X == Y)
            return;
        if(son[X] < son[Y])
            fa[X] = Y;
        else
        {
            fa[Y] = X;
            if(son[X] == son[Y])
                son[X]++;
        }
    }
}dS;

vector <pair<int, int> > G[MAXC];//
vector <int> Adj[MAXC];//
bool used[MAXC];//
int newNo[MAXC];//
int dist[MAXC];//
int allocCnt;//
int N, M;//

void BFS()
{
	queue <int> q;
    memset(dist, 0xFF, sizeof dist);
    q.push(1);
    dist[1] = 0;

    while(!q.empty())
    {
        int cur = q.front();
        q.pop();

        for(auto itr = Adj[cur].begin(); itr != Adj[cur].end(); itr++)
            if(dist[*itr] < 0)
                dist[*itr] = dist[cur]+1,
                q.push(*itr);
    }
}
void read(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    int a, b, c;
    while(~scanf("%d %d",&N,&M))
    {
		
	    for(int i = 1; i <= M; i++)
	    {
			read(a);
			read(b);
			read(c);
	        G[c].push_back(make_pair(a, b));
		}
	    allocCnt = N ;
	    for(int k = 1; k <= MAXC; k++)
	    {
	        int fa;
	        if(G[k].empty())
	            continue;
	
	        for(auto itr = G[k].begin(); itr != G[k].end(); itr++)
	        {
	            used[ITRF] = used[ITRS] = false,
	            newNo[ITRF] = newNo[ITRS] = -1,
	            dS.son[ITRF] = dS.son[ITRS] = 0;
	            dS.fa[ITRF] = ITRF, dS.fa[ITRS] = ITRS;
	        }
	
	        for(auto itr = G[k].begin(); itr != G[k].end(); itr++)
	            dS.union(ITRF, ITRS);
	        for(auto itr = G[k].begin(); itr != G[k].end(); itr++)
	        {
	            if(!used[ITRF])
	            {
	                used[ITRF] = true;
	                fa = dS.find(ITRF);
	                if(newNo[fa] <= 0)
	                    newNo[fa] = ++allocCnt;
	                Adj[ITRF].push_back(newNo[fa]);
	                Adj[newNo[fa]].push_back(ITRF);
	            }
	            if(!used[ITRS])
	            {
	                used[ITRS] = true;
	                fa = dS.find(ITRS);
	                if(newNo[fa] <= 0)
	                    newNo[fa] = ++allocCnt;
	                Adj[ITRS].push_back(newNo[fa]);
	                Adj[newNo[fa]].push_back(ITRS);
	            }
	        }
	    }
	
	    BFS();
	
	    if(dist[N] < 0)
	        printf("-1\n");
	    else
	      	printf("%d\n",dist[N] / 2 );
	    for(int i=0;i<MAXC;i++)
	    {
	    	G[i].clear();
	    	Adj[i].clear();
	    	used[i]=0;
	    	newNo[i]=0;
	    }
	}
}


Measured memory_bytes: 89744