#include<bits/stdc++.h>
using namespace std;
const int N=105;
int read(){
	int a=0;
	char c=getchar();
	while(c<'0'||c>'9')	c=getchar();
	while(c>='0'&&c<='9')	a=a*10+c-'0',c=getchar();
	return a;
}
int ans=-1;
int alpha[4][2]={
	1,0,
	-1,0,
	0,1,
	0,-1
};
int m=read(),n=read();
int t[N][N],t1[N][N];
void dfs(int sum,int x,int y,bool used){
	cout<<x<<' '<<y<<' '<<sum<<endl;
	if(x==0||x>m||y==0||y>m)	return ;
	if(t1[x][y]<=sum)	return;
	t1[x][y]=sum; 
	if(x==m&&y==m){
		ans=sum;
		return ;
	}
	for(int i=0;i<4;i++){
		int x1=x+alpha[i][0],y1=y+alpha[i][1];
		if(t[x1][y1]){
			if(t[x1][y1]==t[x][y])
				dfs(sum,x1,y1,0);
			else
				dfs(sum+1,x1,y1,0);
		}
		else if(used==0){
			t[x1][y1]=t[x][y];	
			dfs(sum+2,x1,y1,1);
			t[x1][y1]=0;
		}
	}
}
int main(){
	for(int i=1;i<=n;i++){
		int x=read(),y=read(),c=read();
		if(c==1)	t[x][y]=2;
		else t[x][y]=1;
		//cout<<x<<' '<<y<<' '<<t[x][y]<<endl;
	}
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)	t1[i][j]=1e9+5;
	dfs(0,1,1,0);
	cout<<ans<<endl;
	return 0;
}