#include<bits/stdc++.h>
using namespace std;

const int maxc=1e6+5;
int n,m,cn;

vector<int>v[2*maxc];//注意大小 
vector<int>col[maxc];
int vis[2*maxc],id[2*maxc],dis[2*maxc];
queue<int>q;

int father[(int)1e5+5];
void rs(int x)
{
	father[x]=x;
	vis[x]=0;
	id[x]=0;
}
void reset()
{
	for(int i=1; i<=n; i++)
	{
		rs(i);
	}
}
int findf(int x)
{
	return father[x]==x?x:father[x]=findf(father[x]);
}
void join(int a,int b)
{
	int x=findf(a),y=findf(b);
	father[x]=y;
}

void pset()
{
	cin>>n>>m;
	for(int i=1; i<=m; i++)
	{
		int p,q,c;
		cin>>p>>q>>c;
		col[c].push_back(p);
		col[c].push_back(q);
	}
	cn=n;
	reset();
	for(int i=1; i<=1e6; i++)
	{
		if(col[i].size()==0)continue;
		for(int k=0; k<col[i].size(); k+=2)
		{
			int p=col[i][k],q=col[i][k+1];
			rs(p);
			rs(q);
		}
		for(int k=0; k<col[i].size(); k+=2)
		{
			int p=col[i][k],q=col[i][k+1];
			join(p,q);
		}
		for(int k=0; k<col[i].size(); k+=2)
		{
			int p=col[i][k],q=col[i][k+1];
			if(!vis[p])
			{
				vis[p]=1;
				int root=findf(p);
				if(!id[root])
				{
					cn++;
					id[root]=cn;
				}
				v[p].push_back(id[root]);
				v[id[root]].push_back(p);
			}
			if(!vis[q])
			{
				vis[q]=1;
				int root=findf(q);
				if(!id[root])
				{
					cn++;
					id[root]=cn;
				}
				v[q].push_back(id[root]);
				v[id[root]].push_back(q);
			}
		}
	}
}

void deal()
{
	q.push(1);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=0; i<v[x].size(); i++)
		{
			if(!dis[v[x][i]])
			{
				dis[v[x][i]]=dis[x]+1;
				q.push(v[x][i]);
			}
		}
	} 
	cout<<(dis[n]==0?-1:(dis[n]/2))<<'\n';
}

int main()
{
	ios::sync_with_stdio(0);
	//cin.tie(0);
	pset();
	deal();

	return 0;
}