#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef pair<int,int> pii;

int n,m;
vector<pii> edge[200200];
vector<int> col[1001000];
vector<int> ned[500500];
int colour[200200],x[200200],l[200200];
int dist[500500];

int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		int p,q,c;
		scanf("%d%d%d",&p,&q,&c);
		edge[p].pb(mp(c,q));
		edge[q].pb(mp(c,p));
		col[c].pb(q);
		col[c].pb(p);
	}
	for (int i=1;i<=n;i++){
		sort(edge[i].begin(),edge[i].end());
	}
	memset(colour,0,sizeof colour);
	memset(x,0,sizeof x);
	memset(l,0,sizeof l);
	int nw=n+1;
	for (int co=1;co<=1000000;co++){
		if (!col[co].size()) continue;
		for (int k=0;k<col[co].size();k++){
			int p=col[co][k];
			if (colour[p]==co) continue;;colour[p]=co;
			queue<int> q;
			q.push(p);
			while (!q.empty()){
				int b=q.front();
				q.pop();
				while (l[b]<edge[b].size()){
					int c=edge[b][l[b]].f;
					if (c!=co) break;
					int pp=edge[b][l[b]].s;
					if (colour[pp]!=co){
						colour[pp]=co;
						q.push(pp);
					}
					l[b]++;
				}
				ned[b].pb(nw);
				ned[nw].pb(b);
			}
			nw++;
		}
	}
	for (int i=1;i<=nw;i++) dist[i]=-2;
	queue<int> q;
	q.push(1);
	dist[1]=0;
	while (!q.empty()){
		int b=q.front();
		q.pop();
		for (int i=0;i<ned[b].size();i++){
			int p=ned[b][i];
			if (dist[p]==-2){
				dist[p]=dist[b]+1;
				q.push(p); 
			}
		}
	} 
	cout<<dist[n]/2<<endl;
	return 0;
}