#include <bits/stdc++.h>
using namespace std;
int m,n,a[101][101],vis[101][101];
void dfs(int x,int y,int x2,int y2,int sum,bool w) {
	vis[x][y]=sum;
	if(x==m&&y==m)return ;
	if(x!=x2+1&&x!=1)
		if(a[x][y]!=a[x-1][y]) {
			if(w==1&&a[x-1][y]==0&&vis[x][y]+2<=vis[x-1][y])dfs(x-1,y,x,y,sum+2,0);
			else if(vis[x][y]+1<=vis[x-1][y])dfs(x-1,y,x,y,sum+1,1);
		} else dfs(x-1,y,x,y,sum,1);
	if(x!=x2-1&&x!=m&&!vis[x+1][y])
		if(a[x][y]!=a[x+1][y]) {
			if(w==1&&a[x+1][y]==0&&vis[x][y]+2<=vis[x+1][y])dfs(x+1,y,x,y,sum+2,0);
			else if(vis[x][y]+1<=vis[x-1][y])dfs(x+1,y,x,y,sum+1,1);
		} else dfs(x+1,y,x,y,sum,1);
	if(y!=y2+1&&y!=1&&!vis[x][y-1])
		if(a[x][y]!=a[x][y-1]) {
			if(a[x][y-1]==0&&w==1&&vis[x][y]+2<=vis[x][y-1])dfs(x,y-1,x,y,sum+2,0);
			else if(vis[x][y]+1<=vis[x-1][y])dfs(x,y-1,x,y,sum+1,1);
		} else dfs(x,y-1,x,y,sum,1);
	if(y!=y2+1&&y!=m&&!vis[x][y-1])
		if(a[x][y]!=a[x][y+1]) {
			if(a[x][y+1]==0&&w==1&&vis[x][y]+2<=vis[x][y+1])dfs(x,y+1,x,y,sum+2,0);
			else if(vis[x][y]+1<=vis[x][y+1])dfs(x,y+1,x,y,sum+1,1);
		} else dfs(x,y+1,x,y,sum,1);
}
int main() {
	scanf("%d%d",&m,&n);
	for(int i=0; i<=m; i++)
		for(int j=0; j<=m; j++)
			vis[i][j]=2147483640;
	for(int i=1,x,y,w; i<=n; i++) {
		scanf("%d%d%d",&x,&y,&w);
		a[x][y]=w+1;
	}
	dfs(1,1,0,0,0,1);
	if(vis[m][m]==2147483640)printf("-1");
	else printf("%d",vis[m][m]);
	return 0;
}

输出2147483640
请求大佬支援