debug必关

#include<bits/stdc++.h>
using namespace std;
int n,m,mp[105][105],ans=INT_MAX;
bool visted[105][105];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y,int c){
    if(x==m&&y==m){
        ans=min(ans,c);
        return;
    }
    visted[x][y]=1;
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=1&&nx<=m&&ny>=1&&ny<=m&&(mp[nx][ny]!=-1||mp[x][y]!=-1)&&visted[nx][ny]==0){
            int t=(mp[x][y]!=mp[nx][ny])?1:0;
            if(mp[nx][ny]==-1)t=2;
            dfs(nx,ny,t+c);
    		visted[nx][ny]=0;
        }
    }
}
int main(){
    cin>>m>>n;
    memset(mp,-1,sizeof(mp));
    for(int i=0;i<n;i++){
    	int x,y,c;
    	cin>>x>>y>>c;
    	mp[x][y]=c;
	}
	dfs(1,1,0);
	if(ans==INT_MAX){
		cout<<-1;
		return 0;
	}
	cout<<ans;
    return 0;
}