#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;
int m, n, x, y, c;
int dist[N][N][2], st[N][N][2];
int mp[110][110];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct node{
    int x;
    int y;
    int clr;
    int v;
    bool operator < (const node &p)const{
        return v > p.v;
    }
};

void dj(){
    dist[1][1][mp[1][1]] = 0;
    priority_queue<node> q;
    q.push({1, 1, mp[1][1], 0});
    while(q.size()){
        auto t = q.top();
        q.pop();
        int x = t.x;
        int y = t.y;
        int clr = t.clr;
        int v = t.v;
        if(st[x][y][clr]) continue;
        st[x][y][clr] = 1;
        for (int i = 0; i < 4; i ++ ){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx < 1 || xx > m || yy < 1 || yy > m || mp[xx][yy] == -1 && mp[x][y] == -1)continue;

            if(mp[xx][yy] == clr && dist[xx][yy][clr] > v){
                dist[xx][yy][clr] = v;
                q.push({xx, yy, clr, v});
            }else if(mp[xx][yy] != -1 && mp[xx][yy] != clr && dist[xx][yy][mp[xx][yy]]>v+1){
                dist[xx][yy][mp[xx][yy]] = v + 1;
                q.push({xx, yy, mp[xx][yy], v+1});
            }else if(mp[xx][yy] == -1 && dist[xx][yy][clr]>v+2){
                dist[xx][yy][clr] = v+2;
                q.push({xx, yy, clr, v + 2});
            }
        }
    }
}

int main(){
    cin >> m >> n;
    memset(mp, -1, sizeof mp);
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; i ++ ){
        cin >> x >> y >> c;
        mp[x][y] = c;
    }

    dj();

    int ans = min(dist[m][m][0], dist[m][m][1]);
    if(ans == INF) cout << -1;
    else cout << ans;

    return 0;
}