#include<bits/stdc++.h>
using namespace std;
#define MAXN (int)(1e5+5)

vector<pair<int,int> > nei[MAXN];
vector<int> cit[1000005];
vector<int>comp;
int col[1000005];
bool vis[1000005];
vector<int>newnei[1000005];
int dp[1000005];
int main()
{
	int n,m;
	cin>>n>>m;
	memset(col,-1,sizeof col);
	for(int i=0;i<m;i++)
	{
		int x,y,c;
		cin>>x>>y>>c;
		x--,y--,c--;
		nei[x].push_back(make_pair(c,y));
		nei[y].push_back(make_pair(c,x));
		cit[c].push_back(x);
		cit[c].push_back(y);
		comp.push_back(c);
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<nei[i].size();j++)
		{
//			cout<<nei[i][j].first<<"&"<<nei[i][j].second<<" ";
		}
//		cout<<endl;
	}
	sort(comp.begin(),comp.end());
	comp.erase(unique(comp.begin(),comp.end()),comp.end());
	for(int i=0;i<n;i++)
	{
		sort(nei[i].begin(),nei[i].end());
	}
	int newci=n;
	for(int i=0;i<comp.size();i++)
	{
		int cmp=comp[i];
		for(int j=0;j<cit[comp[i]].size();j++)
		{
			int v=cit[comp[i]][j];
//			cout<<"v"<<i<<" "<<v<<endl;
			if(col[v]==cmp) continue;
			queue<int> q;
			q.push(v);
			col[v]=cmp;
			vector<int> ciin;
			memset(vis,0,sizeof vis);
			while(!q.empty())
			{
				v=q.front();
				ciin.push_back(v);
				q.pop();
				if(vis[v]) continue;
				vis[v]=1;
				int k=0;
//				cout<<"aaav"<<v<<endl;
				for(;k<nei[v].size();k++)
				{
					if(nei[v][k].first==cmp) break;
				}
				for(;k<nei[v].size();k++)
				{
//					cout<<"wa"<<nei[v][k].first<<" "<<nei[v][k].second<<endl;
					if(nei[v][k].first!=cmp) continue;;
					int u=nei[v][k].second;
//					cout<<u<<" "<<col[u]<<"lala"<<endl;
					if(col[u]==cmp) continue;
					col[u]=cmp;
					q.push(u);
				}
			}
			for(int k=0;k<ciin.size();k++)
			{
				int v=ciin[k];
//				cout<<v<<" "<<newci<<endl;
				newnei[v].push_back(newci);
				newnei[newci].push_back(v);
			}
			newci++;
		}
	}
	queue<int>q;
	for(int i=0;i<n*3;i++) dp[i]=-2;
	dp[0]=1;
	q.push(0);
	while(!q.empty())
	{
		int v=q.front();
		q.pop();
		for(int k=0;k<newnei[v].size();k++)
		{
			int u=newnei[v][k];
			if(dp[u]==-2)
			{
				dp[u]=dp[v]+1;q.push(u);
			}
			
		}
	}
	cout<<dp[n-1]/2;
}