由于cost懒更新，所以在判断其他更有解时，队列中可能有多个坐标相同的元素，如果最优解最后更新对答案无影响，如果最优解先更新，之后被次优解覆盖，则答案错误。 应当在添加判断条件或者避免cost懒更新。 一开始缺少if(t.ct>=cost[t.x][t.y])continue;扣40

node t=q.front();
q.pop();
if(t.ct>=cost[t.x][t.y])continue;
cost[t.x][t.y]=t.ct;

#include<bits/stdc++.h>
#define PII pair<long long int,int>
#define x first
#define y second
using namespace std;
using ll = long long int;
const int N=110;
int n,m;
int st[N][N];
bool vis[N][N];
int res=0;
int cost[N][N];//到达每个点的花费
int mm[][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
struct node{
	int x,y,ct;
	int c;
};
int flag=0;
void bfs(){
	queue<node>q;
	q.push({1,1,0,st[1][1]});
	while(!q.empty()){
		//相同格子+0，不同格子+1，无格子+2
		node t=q.front();
		q.pop();
		if(t.ct>=cost[t.x][t.y])continue;
		cost[t.x][t.y]=t.ct;
		if(t.x==m&&t.y==m)flag=1;
		for(int i=1;i<=4;i++){
			int nx=t.x+mm[i][0],ny=t.y+mm[i][1];
			if(nx<1||ny<1||nx>m||ny>m)continue;
			if(t.c>1&&st[nx][ny]==-1){//上一个格子为空格，当前格子也为空格
				continue;
			}
			
			//0为红，1为黄，2为空格但置为红，3为空格但置为黄
			if(t.c%2==st[nx][ny]){//相同颜色不用花费
				if(t.ct>=cost[nx][ny])continue;
				q.push({nx,ny,t.ct,st[nx][ny]});
			}
			else if(st[nx][ny]!=-1){//不同颜色
				if(t.ct+1>=cost[nx][ny])continue;
				q.push({nx,ny,t.ct+1,st[nx][ny]});
			}
			else if(st[nx][ny]==-1){//当前为空格，但上一个不是空格
				if(t.ct+2>=cost[nx][ny])continue;
				q.push({nx,ny,t.ct+2,t.c+2});
			}			
		}
	}
}
int main(){
	cin>>m>>n;
	int x,y,c;
	memset(cost,0x3f,sizeof(cost));
	memset(st,-1,sizeof(st));
	for(int i=1;i<=n;i++){
		cin>>x>>y>>c;
		st[x][y]=c;
	}
	bfs();
	if(flag)
	cout<<cost[m][m]<<endl;
	else{
		cout<<-1<<endl;
	}
	return 0;
}