#include <bits/stdc++.h>
using namespace std;
long long mapp[10001][10001];long long ret,f[10001][10001],dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1},m,n;
struct point
{
    int x,y,coin,color;
    bool magic;
};
queue <point> q;
void bfs()
{
    point item;
    item.x = 1;
    item.y = 1;
    item.coin = 0;
    item.magic = true;
    item.color = -1;
    q.push(item);
    f[1][1] = 0;
    while(q.empty() == false){
        if(q.front().x == m&&q.front().y == m)
        {
            ret = min(ret,q.front().coin);
            q.pop();
            continue;
        }
        for(int i = 0;i<4;i++){
            int x = q.front().x+dx[i],y = q.front().y+dy[i];
            item.x = x;
            item.y = y;
            if(x>=1&&x<=m&&y>=1&&y<=m){
                if(mapp[x][y]!=-1){
                    if(mapp[x][y] == mapp[q.front().x][q.front().y]||mapp[x][y] == q.front().color) item.coin = q.front().coin;
                    else item.coin = q.front().coin+1;
                    if(item.coin<f[x][y])
                    {
                        item.magic = true;
                        item.color = -1;
                        q.push(item);
                        f[x][y] = item.coin;
                    }
                }
                else{
                    if(q.front().magic){
                        item.magic = false;
                        item.color = mapp[q.front().x][q.front().y];
                        item.coin = q.front().coin+2;
                        if(item.coin<f[x][y])
                        {
                            q.push(item);
                            f[x][y] = item.coin;
                        }
                    }
                }
            }
        }q.pop();
    }
}
int main()
{
    cin >> m >> n;
    memset(mapp,-1,sizeof(mapp));
    memset(f,0x3f,sizeof(f));
    int a,b,c;
    for(int i = 1;i<=n;i++)
    {
        cin >> a >> b >> c;
        mapp[a][b] = c;
    }
    bfs();
    if(f[m][m] == 0x3f3f3f3f) cout << -1;
    else cout << f[m][m];
    return 0;
}

恳求大佬救救蒟蒻QWQ