内存限制256mb，根据数据深搜最多递归到10000层

#include "iostream"
#include "limits.h"
using namespace std;
short a[105][105], m, ans[105][105][2], result=SHRT_MAX;
int n, c;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
void dfs(short x, short y, short pre_x, short pre_y, short cur, short step, bool used){
    if(step>result) return;
    if(x==m && y==m){
        if(step<result) result=step;
        return;
    }
    short nx, ny;
    for(int i=0;i<4;i++){
        nx=x+dx[i], ny=y+dy[i];
        if((nx==pre_x && ny==pre_y) || nx<1 || nx>m || ny<1 || ny>m) continue;

        if(a[nx][ny]==0 && !used){
            if(ans[nx][ny][cur-1]==0 || ans[nx][ny][cur-1]>step+2){
                ans[nx][ny][cur-1]=step+2;
                dfs(nx, ny, x, y, cur, step+2, true);
            }
        }else if(a[nx][ny]==1){
            if(cur==1 && (ans[nx][ny][0]>step || ans[nx][ny][0]==0)){
                ans[nx][ny][0]=step;
                dfs(nx, ny, x, y, 1, step, false);
            }else if(cur==2 && (ans[nx][ny][0]>step+1 || ans[nx][ny][0]==0)){
                ans[nx][ny][0]=step+1;
                dfs(nx, ny, x, y, 1, step+1, false);
            }
        }else if(a[nx][ny]==2){
            if(cur==1 && (ans[nx][ny][1]>step+1 || ans[nx][ny][1]==0)){
                ans[nx][ny][1]=step+1;
                dfs(nx, ny, x, y, 2, step+1, false);
            }else if(cur==2 && (ans[nx][ny][1]>step || ans[nx][ny][1]==0)){
                ans[nx][ny][1]=step+1;
                dfs(nx, ny, x, y, 2, step, false);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> n;
    short x, y;
    for(int i=1;i<=n;i++){
        cin >> x >> y >> c;
        a[x][y]=c+1;
    }
    if(a[1][1]==0){
        cout << "-1";
        return 0;
    }
    dfs(1, 1, -100, -100, a[1][1], 0, false);
    cout << result << "\n";
}