#include <bits/stdc++.h> 

using namespace std;
int ans=999999 ;
int x[4]={1,-1,0,0};
	int y[4]={0,0,1,-1}; 
 	int n = 0,m=0;int a[101][101]={0};int color[101][101]={-1}; int b=0,c=0,d=0 ;
int shensou(int x2,int y2, int col,int z,int M)
{   int x1,y1;  if(x2==m&&y2==m)
	{
	   if(M<ans)ans=M;
}
else{
 
		for(int i = 0;i<4;i++)
	{   
		x1=x2+x[i];
		y1=y2+y[i];
		if(x1>=1&&x1<=m&&y1>=1&&y1<=m&&a[x1][y1]>M)
		{  
			if(color[x1][y1]>=0)
			{
				if(color[x1][y1]==col)
				{
					a[x1][y1]=M;shensou(x1,y1,col,0,M);
				}
				else {
				  a[x1][y1]=M+1;shensou(x1,y1,(col+1)%2,0,M+1);
				}
			}
			else {
				if(z==0&&a[x1][y1]>M+2)
				{
					a[x1][y1]=M+2;shensou(x1,y1,col,1,M+2);
				}
			}
		}
	} }
}
int main(void)
{    
	
	freopen("checkerboard.in","r",stdin);  	freopen("checkerboard.out","w",stdout);
	cin>>m>>n;
	for(int i=1;i<m+1;i++)
	 for(int j = 1;j<m+1;j++)
	 {
	 	color[i][j]=-1;a[i][j]=99999;
	 }
	 
	for(int i = 1;i<n+1;i++)
	{  
		cin>>b>>c>>d;color[b][c]=d;
	 
	}

	 shensou(1,1,color[1][1],0,0);
	 if(ans==999999)
	 {
	 	cout<<-1;
	 }
	 else cout<<ans;
   
}