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

// 棋盘最大尺寸，适配m≤100的要求
const int MAXN = 105;
// 无穷大常量，用于初始化距离数组
const int INF = 0x3f3f3f3f;
// 四个移动方向：上、下、左、右
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int color[MAXN][MAXN];  // 棋盘颜色：-1=无色，0=红色，1=黄色
int dist[MAXN][MAXN][3];// dist[x][y][state]：到达(x,y)的state状态的最小花费
int m;                  // 棋盘大小m×m

int main()
{
    // 关闭cin同步，加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    // [1] 读取棋盘大小m、有颜色的格子数量n
    cin >> m >> n;

    // [2] 初始化棋盘为无色(-1)
    memset(color, -1, sizeof(color));
    // 读取n个有颜色的格子
    for(int i = 0; i < n; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        color[x][y] = c;
    }

    // [3] 初始化距离数组为无穷大
    memset(dist, 0x3f, sizeof(dist));
    // 起点(1,1)是原生有颜色的，state=0，初始花费0
    dist[1][1][0] = 0;

    // [4] Dijkstra优先队列：小根堆，存储(当前花费, x坐标, y坐标, 状态)
    priority_queue<tuple<int, int, int, int>, vector<tuple<int, int, int, int>>, greater<tuple<int, int, int, int>>> pq;
    pq.emplace(0, 1, 1, 0);

    // [5] Dijkstra核心循环
    while(!pq.empty())
    {
        auto [cur_cost, x, y, state] = pq.top();
        pq.pop();

        // 剪枝：当前状态的花费已经大于记录的最小值，直接跳过
        if(cur_cost > dist[x][y][state]) continue;

        // 获取当前格子的颜色
        int cur_c;
        if(state == 0) cur_c = color[x][y]; // 原生格子，取原生颜色
        else if(state == 1) cur_c = 0;      // 临时格子，颜色0
        else cur_c = 1;                      // 临时格子，颜色1

        // 遍历四个移动方向
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 合法性校验：坐标在棋盘范围内
            if(nx < 1 || nx > m || ny < 1 || ny > m) continue;

            // ========== 情况1：当前在原生格子，可使用魔法 ==========
            if(state == 0)
            {
                // 子情况1a：移动到相邻的原生有颜色格子
                if(color[nx][ny] != -1)
                {
                    // 计算移动花费：同色0，不同色1
                    int cost = (cur_c == color[nx][ny]) ? 0 : 1;
                    // 新状态：原生格子，可使用魔法
                    if(dist[nx][ny][0] > cur_cost + cost)
                    {
                        dist[nx][ny][0] = cur_cost + cost;
                        pq.emplace(dist[nx][ny][0], nx, ny, 0);
                    }
                }
                // 子情况1b：对相邻的无色格子使用魔法
                else
                {
                    // 选择1：把无色格子染成0
                    int cost1 = 2 + (cur_c != 0); // 魔法2金币 + 移动花费
                    if(dist[nx][ny][1] > cur_cost + cost1)
                    {
                        dist[nx][ny][1] = cur_cost + cost1;
                        pq.emplace(dist[nx][ny][1], nx, ny, 1);
                    }
                    // 选择2：把无色格子染成1
                    int cost2 = 2 + (cur_c != 1); // 魔法2金币 + 移动花费
                    if(dist[nx][ny][2] > cur_cost + cost2)
                    {
                        dist[nx][ny][2] = cur_cost + cost2;
                        pq.emplace(dist[nx][ny][2], nx, ny, 2);
                    }
                }
            }
            // ========== 情况2：当前在临时格子，不可使用魔法 ==========
            else
            {
                // 只能移动到相邻的原生有颜色格子
                if(color[nx][ny] != -1)
                {
                    // 计算移动花费：同色0，不同色1
                    int cost = (cur_c == color[nx][ny]) ? 0 : 1;
                    // 新状态：原生格子，可使用魔法
                    if(dist[nx][ny][0] > cur_cost + cost)
                    {
                        dist[nx][ny][0] = cur_cost + cost;
                        pq.emplace(dist[nx][ny][0], nx, ny, 0);
                    }
                }
            }
        }
    }

    // [6] 计算终点的最小花费：三种状态取最小值
    int ans = min({dist[m][m][0], dist[m][m][1], dist[m][m][2]});
    // 如果最小值还是无穷大，说明无法到达，输出-1，否则输出最小值
    cout << (ans == INF ? -1 : ans) << '\n';

    return 0;
}