#include<bits/stdc++.h>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
//251103FD
using namespace std;
#define PB pop_back
#define PF pop_front
#define np next_permutation
#define eb emplace_back
#define bf push_front
#define mp make_pair
#define s second
#define f first
#define mt make_tuple
#define foreach(it, a) for(__typeof((a).begin()) it=(a).begin(); it!=(a).end(); it++)
#define forn(i, a) for(int i=0; i<a; i++)
#define Forn(i, a) for(int i=1; i<=a; i++)
#define read(x) ((scanf("%s", &_), (x) = _))
#define INF 1e9
#define memINF 127
#define inf 1e18
#define all(x) x.begin(), x.end()
#define MOD 1e9+7 
#define HASH 1543 

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<pi,int> pii;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef unsigned int uint;

using namespace std;

inline int in() 
{
    int x=0, c;
    for(; (uint)((c=getchar())-'0')>=10;) 
	{ 
		if(c=='-') 
			return -in(); 
		if(!~c)
			throw ~0; 
	}
    do 
	{ 
		x=(x<<3)+(x<<1)+(c^48); 
	} 
	while((uint)((c=getchar())^48)<10);
    return x;
}
inline int gcd(int a, int b){if(a>b) swap(a, b); return a==0?b:gcd(b%a, a);}
inline int lcm(int a, int b){return a*b/gcd(a, b);}

int N, M, par[1000010], ranks[1000010], a, b, c, dist[1000010], all, newNode[1000010];
vector<pi> e[1000010];
vi adj[1000010];
bool used[1000010];
set<int> cost;

inline int find(int x)
{
	return par[x]==x?x:par[x]=find(par[x]);
}

inline void unite(int x, int y)
{
	x=find(x), y=find(y);
	if(x==y)
		return;
	if(ranks[x]<ranks[y])
		par[x]=y;
	else
	{
		par[y]=x;
		if(ranks[x]==ranks[y])
			ranks[x]++;
	}
}

int main()
{
	while(~scanf("%d %d",&N,&M))
	{
		while(M--)
		{
			a=in(), b=in(), c=in();
			e[c].eb(mp(a, b));
			cost.insert(c);
		}
		all=N;
		foreach(ii, cost)
		{
			int i=*ii;
			if(!e[i].size())
				continue;
			int pa;
			foreach(it, e[i])
	        {
	            used[it->f]=used[it->s]=false,
	            newNode[it->f]=newNode[it->s]=-1,
	            ranks[it->f]=ranks[it->s]=0;
	            par[it->f]=it->f;
				par[it->s]=it->s;
	        }
			foreach(it, e[i])
				unite(it->f, it->s);
			foreach(it, e[i])
	        {
	            if(!used[it->f])
	            {
	                used[it->f]=true;
	                pa=find(it->f);
	                if(newNode[pa]<=0)
	                    newNode[pa]=++all;
	                adj[it->f].eb(newNode[pa]);
	                adj[newNode[pa]].eb(it->f);
	            }
	            if(!used[it->s])
	            {
	                used[it->s]=true;
	                pa=find(it->s);
	                if(newNode[pa]<=0)
	                    newNode[pa]=++all;
	                adj[it->s].eb(newNode[pa]);
	                adj[newNode[pa]].eb(it->s);
	            }
	        }
		}
		queue<int> q;
		q.push(1);
		memset(dist, -1, sizeof(dist));
		dist[1]=0;
		while(!q.empty())
		{
			int cur=q.front();
			q.pop();
			foreach(it, adj[cur])
				if(dist[*it]<0)
					dist[*it]=dist[cur]+1, q.push(*it);
		}
		if(dist[N]<0)
			puts("-1");
		else
			printf("%d\n", dist[N]>>1);
		forn(i, all+1)
	    {
	    	e[i].clear();
	    	adj[i].clear();
	    	used[i]=0;
	    	newNode[i]=0;
	    }
	    cost.clear();
	}
	return 0;
}

Measured memory_bytes: 81408