#include<bits/stdc++.h>
using namespace std;
int dx[8]={0,0,1,-1};
int dy[8]={1,-1,0,0};
int a[101][101],n,m,minn=1000000000;
bool b[101][101];
void dfs(int x,int y,int k,int f)
{
	b[x][y]=1;
	if(x==n&&y==n)
	{
		minn=min(minn,k);
		return;
	}
	for(int i=0;i<4;++i)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&b[nx][ny]==0)
		{
			if(a[nx][ny]==a[x][y])
			{
				dfs(nx,ny,k,0);
			}
			else if(a[nx][ny]!=a[x][y]&&a[nx][ny]!=-1)
			{
				dfs(nx,ny,k+1,0);
			}
			else if(a[nx][ny]==-1&&f==0)
			{
				int p=a[x][y];
				a[nx][ny]=a[x][y];
				dfs(nx,ny,k+2,1);
				a[nx][ny]=p;
			}
		}
	}
}
int main()
{
	memset(a,-1,sizeof(a));
	cin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		int x,y,clr;
		cin>>x>>y>>clr;
		a[x][y]=clr;
	}
	dfs(1,1,0,0);
	if(minn==1000000000) cout<<-1;
	else cout<<minn<<endl;
	return 0;
}