wa了四个

#define ll long long
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
const ll inf=0x7fffffff;
ll a[101][101],book[101][101],ans[101][101],n,m;
ll u,v,w,flag=0,minn=inf;
void dfs(ll x,ll y,ll colour,ll money){
	ll next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
	ll dx,dy,k;
	if(money>=ans[x][y]){
		return ;
	}
	ans[x][y]=money;
	if(x==m&&y==m){
		if(money<minn){
			minn=money;
		}
		flag=1;
		return ;
	}
	for(k=0;k<=3;k++){
		dx=x+next[k][0];
		dy=y+next[k][1];
		if(dx<1||dx>m||dy<1||dy>m||book[dx][dy]==1){
			continue;
		}
		if(colour==1){ 
			if(a[dx][dy]==-1){
				continue;
			}
			if(a[dx][dy]!=-1&&book[dx][dy]==0){
				if(a[x][y]==a[dx][dy]&&book[dx][dy]==0){
					book[dx][dy]=1;
					dfs(dx,dy,0,money);
					book[dx][dy]=0;
				}
				else if(a[x][y]!=a[dx][dy]&&book[dx][dy]==0){
					book[dx][dy]=1;
					dfs(dx,dy,0,money+1);
					book[dx][dy]=0;
				}
				a[x][y]=-1;
			}
		}
		else { 
			if(a[dx][dy]==-1&&book[dx][dy]==0){
				book[dx][dy]=1;
				
				a[dx][dy]=0;
				if(a[dx][dy]==a[x][y])dfs(dx,dy,1,money+2);
				else dfs(dx,dy,1,money+3);
				
				a[dx][dy]=1;
				if(a[dx][dy]==a[x][y])dfs(dx,dy,1,money+2);
				else dfs(dx,dy,1,money+3);
				
				a[dx][dy]=-1;
				book[dx][dy]=0;
			}
			else if(a[x][y]==a[dx][dy]&&book[dx][dy]==0){
				book[dx][dy]=1;
				dfs(dx,dy,0,money);
				book[dx][dy]=0;
			}
			else if(a[x][y]!=a[dx][dy]&&book[dx][dy]==0){
				book[dx][dy]=1;
				dfs(dx,dy,0,money+1);
				book[dx][dy]=0;
			}
		}
	}
	return ;
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=-1;
			ans[i][j]=inf;
		}
	}
	for(int i=1;i<=n;i++){
		cin>>u>>v>>w;
		a[u][v]=w;
	}
	dfs(1,1,0,0);
//	if(flag==0)cout<<-1;
//	else cout<<minn;
	if(ans[m][m]!=inf)cout<<ans[m][m];
	else cout<<-1;
	return 0;
}