输出的比数据小1。

#include<bits/stdc++.h>
#define ll long long
#define inf 0x7fffffff
using namespace std;
const ll MAXM=105; 
ll m,n,x,y,c,a[MAXM][MAXM],idx[5]={0,-1,1},idy[5]={0,0,0,-1,1},f[MAXM][MAXM];
bool p[MAXM][MAXM];
struct node{
	ll h,l,s,c;
};
queue<node> q;
bool oks(ll x,ll y,ll z,ll c){
	if(x+idx[z]<1||x+idx[z]>m||y+idy[z]<1||y+idy[z]>m) return false;
	if(!a[x][y]&&!a[x+idx[z]][y+idy[z]]) return false;
	ll coin=0;
	if(!a[x+idx[z]][y+idy[z]]) coin=2;
	else if(a[x+idx[z]][y+idy[z]]!=c) coin=1;
	if(f[x][y]+coin>=f[x+idx[z]][y+idy[z]]) return false;
	f[x+idx[z]][y+idy[z]]=f[x][y]+coin;
	return true;
}
void spfa(){
	node t={0};
	q.push({1,1,0,a[1][1]});
	f[1][1]=0;
	p[1][1]=true;
	while(!q.empty()){
		t=q.front(); q.pop();
		p[t.h][t.l]=false;
		for(int i=1;i<=4;i++){
			if(oks(t.h,t.l,i,t.c)&&!p[t.h+idx[i]][t.l+idy[i]]){
				p[t.h][t.l]=true;
				ll tc=a[t.h+idx[i]][t.l+idy[i]];
				if(!tc) tc=a[t.h][t.l];
				q.push({t.h+idx[i],t.l+idy[i],f[t.h+idx[i]][t.l+idy[i]],tc});
			}
		}
	}
	return;
} 
int main(){
	memset(f,127/3,sizeof(f));
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&x,&y,&c);
		a[x][y]=c+1;
	}
	spfa();
	if(f[m][m]<=inf) printf("%lld",f[m][m]);
	else printf("-1");
	return 0;
}