#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const int M=1000005;
int dis[N+M];
vector<int>e[N+M];
queue<int>qu;
int main()
{
	int n,m,p,q,c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&p,&q,&c);
		e[p].push_back(c+N);
		e[q].push_back(c+N);
		e[c+N].push_back(p);
		e[c+N].push_back(q);
	}
	memset(dis,-1,sizeof(dis));
	dis[1]=0;
	qu.push(1);
	while(!qu.empty())
	{
		int k=qu.front();
		qu.pop();
		for(int i=0;i<e[k].size();i++)
		{
			int v=e[k][i];
			if(dis[v]==-1||dis[v]>dis[k]+1)
			{
				dis[v]=dis[k]+1;
				qu.push(v); 
			}
		}
	}
	if(dis[n]!=-1)
		dis[n]>>=1;
	printf("%d\n",dis[n]);
	return 0;
}
