#include<bits/stdc++.h>
#define fr(j,n) for(int i=j;i<=n;i++)
#define N 1005
using namespace std;
int m,n,ans;
int a[N][N];
bool fd[N][N],f[N][N];
void dfs(int x,int y){
	fd[x][y]=1;
	if(x==m&&y==m)return ;
	if(f[x+1][y])a[x+1][y]=-1;
	else if(f[x-1][y])a[x-1][y]=-1;
	else if(f[x][y+1])a[x][y+1]=-1;
	else if(f[x][y-1])a[x][y-1]=-1;
	if(a[x+1][y]==a[x][y]&&!fd[x+1][y]&&x+1<=m&&y<=m)dfs(x+1,y);
	else if(a[x-1][y]==a[x][y]&&!fd[x-1][y]&&x-1<=m&&y<=m)dfs(x-1,y);
	else if(a[x][y+1]==a[x][y]&&!fd[x][y+1]&&x<=m&&y+1<=m)dfs(x,y+1);
	else if(a[x][y-1]==a[x][y]&&!fd[x][y-1]&&x<=m&&y-1<=m)dfs(x,y-1);
	else if(a[x+1][y]!=-1&&!fd[x+1][y]&&x+1<=m&&y<=m)ans++,dfs(x+1,y);
	else if(a[x-1][y]!=-1&&!fd[x-1][y]&&x-1<=m&&y<=m)ans++,dfs(x+1,y);
	else if(a[x][y+1]!=-1&&!fd[x][y+1]&&x<=m&&y+1<=m)ans++,dfs(x,y+1);
	else if(a[x][y-1]!=-1&&!fd[x][y-1]&&x<=m&&y-1<=m)ans++,dfs(x,y-1);
	else if(!f[x-1][y]&&!f[x][y-1]&&!f[x+1][y]&&!f[x][y+1]){
		if(!fd[x+1][y]&&x+1<=m&&y<=m)ans+=2,f[x][y]=1,a[x+1][y]=a[x][y],dfs(x+1,y);
		else if(!fd[x][y+1]&&x<=m&&y+1<=m)ans+=2,f[x][y]=1,a[x][y+1]=a[x][y],dfs(x,y+1);
		else if(!fd[x-1][y]&&x-1<=m&&y<=m)ans+=2,f[x][y]=1,a[x-1][y]=a[x][y],dfs(x-1,y);
		else if(!fd[x][y-1]&&x<=m&&y-1<=m)ans+=2,f[x][y]=1,a[x][y-1]=a[x][y],dfs(x,y-1);
		else{
			ans=-1;
			return;
		}
	}
	else ans=-1;
	return;
}
int main(){
	scanf("%d%d",&m,&n);
	memset(a,-1,sizeof(a));
	fr(1,n){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		a[x][y]=w;
	}
	dfs(1,1);
	cout<<ans;
	return 0;
}

没TLE就很离谱