https://www.luogu.com.cn/record/156401550

#include<bits/stdc++.h>
using namespace std;
struct point{
	int x,y,c;
	bool magic;
};
int n,m,col[110][110],b[110][110],ans=0x7fffffff,dx[]={0,0,1,-1},dy[]={1,-1,0,0},tmp;
void bfs(){
	queue<point> q;
	q.push({1,1,col[1][1],0});
	b[1][1]=0;
	while(!q.empty()){
		point t=q.front();
		q.pop();
		int x=t.x,y=t.y,c=t.c;
		bool u=t.magic;
//		printf("f:\t%d\t%d\t%d\t%d\t%d\n",x,y,c,u,b[x][y]);
		if(x==n&&y==n){
			ans=min(ans,b[x][y]);
			continue;
		}
		for(int i=0;i<4;i++){
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<=0||tx>n||ty<=0||ty>n) continue;
			if(col[tx][ty]==-1&&u) continue;
			if(col[tx][ty]==c) tmp=b[x][y];
			else if(col[tx][ty]!=-1) tmp=b[x][y]+1;
			else tmp=b[x][y]+2;
			if(tmp<b[tx][ty]||b[tx][ty]==0x7fffffff){
//				printf("tmp=%d\n",tmp);
				if(col[tx][ty]!=-1) q.push({tx,ty,col[tx][ty],0});
				else q.push({tx,ty,c,1});
				b[tx][ty]=tmp;
			}
//			printf("%d\t%d\t%d\t%d\t%d\n",tx,ty,col[tx][ty],u,b[tx][ty]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fill(col[i],col[i]+n+1,-1);
	for(int i=1;i<=n;i++) fill(b[i],b[i]+n+1,0x7fffffff);
	for(int i=1,j,k,l;i<=m;i++){
		scanf("%d%d%d",&j,&k,&l);
		col[j][k]=l;
	}
	bfs();
	printf("%d\n",ans==0x7fffffff?-1:ans);
}