#include<iostream>
using namespace std;
int n,m,a[105][105],used[105][105],f[105][105],ans=0x7ffffffff,bx[10]={0,1,-1},by[10]={0,0,0,1,-1};
void dfs(int x,int y,int num,int last){
	if(used[x][y]==1){
		return;
	}
	if(x<1||x>m||y<1||y>m){
		return;
	}
	if(f[x][y]>num){
		f[x][y]=num;
	}else{
		return;
	}
	if(x==m&&y==m){
		ans=min(ans,num);
		return;
	}
	used[x][y]=1;
	for(int i=1;i<=4;i++){
		int nx=x+bx[i],ny=y+by[i];
		if(a[nx][ny]==0){
			if(a[x][y]!=0){
				dfs(nx,ny,num+2,a[x][y]);
			}
		}else if(a[x][y]==0){
			if(last!=a[nx][ny]){
				dfs(nx,ny,num+1,a[x][y]);
			}else{
				dfs(nx,ny,num,a[x][y]);
			}
		} 
		else{
			if(a[nx][ny]!=a[x][y]){
				dfs(nx,ny,num+1,a[x][y]);
			}
			else{
				dfs(nx,ny,num,a[x][y]);
			}
		} 
	}
	used[x][y]=0;
	return;
} 
int main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			f[i][j]=0x7ffffffff;
		}
	}
	for(int i=1;i<=n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=z+1;
	}
	dfs(1,1,0,a[1][1]);
	if(ans!=0x7ffffffff)cout<<ans;
	else cout<<"-1";
	return 0;
}