#include<iostream> 
#include<cstdio> 
using namespace std; 
int x[6]={-1,1,0,0},y[6]={0,0,-1,1}; 
int f[1000][1000]; 
int a,b,c,ans=99999999; 
int m,n; 
int color[1000][1000]={-1};
void dfs(int x1,int y1,int col,int z,int M) 
{ 
	int tx,ty; 
	if(x1==m&&y1==m) 
	{ 
		if(M<ans) ans=M; 
	} 
	else 
	{ 
		for(int r=0;r<4;r++) 
		{ 
			tx=x1+x[r];
			ty=y1+y[r];
			if((tx>=1&&tx<=m)&&(ty>=1&&ty<=m)&&(f[tx][ty]>M))
				{ 
					if(color[tx][ty]>=0)
						{ 
							if(color[tx][ty]==col)
								{
									f[tx][ty]=M; dfs(tx,ty,col,0,M); 
								} 
							else 
							{
								f[tx][ty]=M+1;
								dfs(tx,ty,(col+1)%2,0,M+1); 
							} 
						} 
					else 
					{
						if(z==0&&f[tx][ty]>M+2) 
						{
							f[tx][ty]=M+2; dfs(tx,ty,col,1,M+2); 
						} 
					} 
			} 
		} 
	} 
} 
int main()
{ 
	freopen("checkerboard.in","r",stdin); 
	freopen("checkerboard.out","w",stdout);
	cin>>m>>n; 
	for(int i=1;i<=m;i++) 
		for(int j=1;j<=m;j++)
			{
				color[i][j]=-1; f[i][j]=999999; 
			} 
	for(int i=1;i<=n;i++) 
	{
		cin>>a>>b>>c; color[a][b]=c; 
	} 
	dfs(1,1,color[1][1],0,0); 
	if(ans==99999999) 
		cout<<-1; 
	else cout<<ans;
	return 0; 
}