#include <bits/stdc++.h>
using namespace std ;
const int N = 1234567;
vector <pair<int,int> > G[N] ;
vector <int> newg[N] ;
queue <int> q ;
int f[N],son[N],id[N],dp[N] ;
bool use[N] ;
int n,m ;
inline void init(int i){
	f[i]=i;son[i]=0;id[i]=-1;use[i]=false ;
}
int find(int x){
	return (x==f[x])?x:f[x]=find(f[x]) ; 
}
inline void merge(int x,int y){
	int X=find(x),Y=find(y) ;
	if (X==Y) return ;
	if (son[X]<son[Y]) f[X]=Y ;//避免被hack 
	else {
		f[Y]=X ;
		if (son[X]==son[Y]) son[X]++ ;
	}
} 
inline int read(){
	char c;int f=1 ;
	while ((c=getchar())<'0' || c>'9') if (c=='-') f=-1 ;
	int res=c-'0' ;
	while ((c=getchar())>='0' && c<='9') res=res*10+c-'0' ;
	return res*f ; 
}
int main(){
	n=read();m=read() ;
	for (int i=1;i<=m;i++){
		int a,b,c ;
		a=read();b=read();c=read() ;
		G[c].push_back(make_pair(a,b)) ;
	}
	int cnt=n; 
	for (int i=1;i<=N;i++){
		if (G[i].empty()) continue ; //无该公司 
		for (int j=0;j<G[i].size();j++){ //初始 
			init(G[i][j].first) ;
			init(G[i][j].second) ;
		}
		for (int j=0;j<G[i].size();j++) merge(G[i][j].first,G[i][j].second) ;
		for (int j=0;j<G[i].size();j++){
			if (!use[G[i][j].first]){
				use[G[i][j].first]=true ;
				int X=find(G[i][j].first) ;
				if (id[X]==-1) id[X]=++cnt ;
				newg[G[i][j].first].push_back(id[X]) ;//该站点与公司建无向边 
				newg[id[X]].push_back(G[i][j].first) ;
			}
			if (!use[G[i][j].second]){ //同样的工作在second上再做一遍 
				use[G[i][j].second]=true ;
				int X=find(G[i][j].second) ;
				if (id[X]==-1) id[X]=++cnt ;
				newg[G[i][j].second].push_back(id[X]) ;
				newg[id[X]].push_back(G[i][j].second) ;
			}
		}
 	}
 	q.push(1) ;
 	memset(dp,-1,sizeof(dp)) ;
 	dp[1]=0; //初始在0号节点
	while(!q.empty()){ //BFS 
		int v=q.front();q.pop() ;
		for (int i=0;i<newg[v].size();i++){
			int to=newg[v][i] ;
			if (dp[to]==-1){ //还没访问 
				dp[to]=dp[v]+1 ;
				q.push(to) ;
			}
		}
	}
	if (dp[n]==-1) cout<<-1 ;
	else cout<<dp[n]/2 ;
}