#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int m, n;
int grid[102][102]; // 1-based索引，-1表示无色，0红色，1黄色
int dist[102][102][2][2]; // dist[x][y][can_magic][current_color]

// 上下左右四个方向
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// 状态结构体，用于优先队列
struct State {
    int cost, x, y, can_magic, color;
    State(int c, int x_, int y_, int cm, int cl) : cost(c), x(x_), y(y_), can_magic(cm), color(cl) {}
    bool operator>(const State& other) const {
        return cost > other.cost; // 小根堆，按花费升序
    }
};

int main() {
    cin >> m >> n;
    memset(grid, -1, sizeof(grid)); // 初始化棋盘为无色

    // 读取有颜色的格子
    for (int i = 0; i < n; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        grid[x][y] = c;
    }

    // 初始化距离数组为无穷大
    for (int x = 1; x <= m; ++x) {
        for (int y = 1; y <= m; ++y) {
            for (int cm = 0; cm < 2; ++cm) {
                for (int cl = 0; cl < 2; ++cl) {
                    dist[x][y][cm][cl] = INF;
                }
            }
        }
    }

    // 起点(1,1)的颜色（题目保证有颜色）
    int start_color = grid[1][1];
    priority_queue<State, vector<State>, greater<State>> pq;
    dist[1][1][1][start_color] = 0; // 初始状态：可使用魔法，花费0
    pq.emplace(0, 1, 1, 1, start_color);

    int ans = INF;

    while (!pq.empty()) {
        State s = pq.top();
        pq.pop();

        int cost = s.cost;
        int x = s.x;
        int y = s.y;
        int can_magic = s.can_magic;
        int color = s.color;

        // 到达终点，更新最小花费
        if (x == m && y == m) {
            ans = min(ans, cost);
            continue;
        }

        // 若当前花费已大于已知最小，跳过
        if (cost > dist[x][y][can_magic][color]) {
            continue;
        }

        // 探索四个方向
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx < 1 || tx > m || ty < 1 || ty > m) {
                continue; // 超出棋盘范围
            }

            int cell_color = grid[tx][ty];
            if (cell_color != -1) { // 目标格子有颜色
                // 计算新花费：颜色不同则+1
                int new_cost = cost + (color != cell_color ? 1 : 0);
                int new_can_magic = 1; // 移动到有颜色格子，可再次使用魔法
                int new_color = cell_color;

                // 更新距离并加入队列
                if (new_cost < dist[tx][ty][new_can_magic][new_color]) {
                    dist[tx][ty][new_can_magic][new_color] = new_cost;
                    pq.emplace(new_cost, tx, ty, new_can_magic, new_color);
                }
            } else { // 目标格子无色，需使用魔法（若允许）
                if (can_magic) { // 当前可使用魔法
                    // 花费2金币，将无色格子变为当前颜色（同色无额外花费）
                    int new_cost = cost + 2;
                    int new_can_magic = 0; // 魔法后不可连续使用
                    int new_color = color;

                    if (new_cost < dist[tx][ty][new_can_magic][new_color]) {
                        dist[tx][ty][new_can_magic][new_color] = new_cost;
                        pq.emplace(new_cost, tx, ty, new_can_magic, new_color);
                    }
                }
            }
        }
    }

    // 输出结果
    cout << (ans == INF ? -1 : ans) << endl;

    return 0;
}
/**************************************************************
	Problem: 1483
	User: zhengzihao
	Language: C++
	Result: Accepted
	Time:78 ms
	Memory:2280 kb
****************************************************************/