#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include<vector>
#include <string.h>
#include <queue>

using namespace std;

int mapp[222][222], color[222][222];
int step[4][2] = {{1,  0},
                  {-1, 0},
                  {0,  -1},
                  {0,  1}};

int m, n;
struct Point {
    int x, y, gold, status, color;
};
queue<Point> pq;

bool check(int x, int y) {
    return x >= 1 && y >= 1 && x <= m && y <= m;
}

void bfs() {
    while (!pq.empty()) {
        auto t = pq.front();
        pq.pop();
        if (t.gold > mapp[t.x][t.y]) {
            continue;
        }
        //cout << t.x << " " << t.y << " " << t.gold << " " << t.status << endl;
        for (int i = 0; i < 4; ++i) {
            if (check(t.x + step[i][0], t.y + step[i][1])) {
                if (t.status == 0 && color[t.x + step[i][0]][t.y + step[i][1]] == 0) {
                    if (t.gold + 2 < mapp[t.x + step[i][0]][t.y + step[i][1]]) {
                        mapp[t.x + step[i][0]][t.y + step[i][1]] = t.gold + 2;
                        Point tt = {t.x + step[i][0], t.y + step[i][1], t.gold + 2, 1, t.color};
                        pq.push(tt);
                    }
                } else if (color[t.x + step[i][0]][t.y + step[i][1]] == t.color &&
                           color[t.x + step[i][0]][t.y + step[i][1]] != 0) {
                    if (t.gold < mapp[t.x + step[i][0]][t.y + step[i][1]]) {
                        mapp[t.x + step[i][0]][t.y + step[i][1]] = t.gold;
                        Point tt = {t.x + step[i][0], t.y + step[i][1], t.gold, 0,t.color};
                        pq.push(tt);
                    }
                } else if (color[t.x + step[i][0]][t.y + step[i][1]] != t.color &&
                           color[t.x + step[i][0]][t.y + step[i][1]] != 0) {
                    if (t.gold + 1 < mapp[t.x + step[i][0]][t.y + step[i][1]]) {
                        mapp[t.x + step[i][0]][t.y + step[i][1]] = t.gold + 1;
                        Point tt = {t.x + step[i][0], t.y + step[i][1], t.gold + 1, 0,color[t.x + step[i][0]][t.y + step[i][1]]};
                        pq.push(tt);
                    }
                }

            }

        }

    }
}

int main() {
    cin >> m >> n;

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            mapp[i][j] = 99999999;
        }
    }
    for (int i = 0; i < n; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        color[x][y] = c + 1;
    }
    Point t = {1, 1, 0, 0, color[1][1]};
    mapp[1][1] = 0;
    pq.push(t);
    bfs();
    if(mapp[m][m]==99999999){
        cout<<-1<<endl;
    }else{
        cout << mapp[m][m] << endl;
    }
    return 0;
}

开到1050就AC了。。