#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
queue<pair<PII,int>> q; // 同时记录下坐标和颜色
map<PII, int> um; // 标记某点处真实颜色
map<PII, int> cost;
int xm[4] = { 1,0,-1,0 };
int ym[4] = { 0,1,0,-1 }; // 四面
int m, n, x, y, c;
//   um[{x,y}]  um[{a,b}]  um[{t.first,t.second}]
//   um[{t.first.first,t.first.second}] // 真实颜色
//   q中有可能放置虚拟颜色
int bfs(int x, int y)
{
    q.push({ { x,y }, um[{x, y}] });
    cost[{x, y}] = 1; // 初始权值为0
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int a = t.first.first + xm[i]; int b = t.first.second + ym[i];
            if (a < 1 || a > m || b < 1 || b > m ||(cost[{a, b}] && cost[{t.first.first,t.first.second}] >= cost[{a,b}])) continue;
            int cs = um[{a, b}]; int cf = t.second; // cf : 父节点的虚拟颜色
            if(!cost[{a, b}]) cost[{a, b}] = 0x3f3f3f3f; // 子节点的初始值视为无穷大
            if (cs && cs == cf) // 颜色相同
            {
                cost[{a, b}] = min(cost[{a, b}],cost[{t.first.first, t.first.second}]);
                q.push({ { a,b }, cs});
            }
            else if (cs && cf && cs != cf) //不同色
            {
                cost[{a, b}] = min(cost[{a, b}]  , cost[{t.first.first, t.first.second}] + 1);
                q.push({ { a,b }, cs});
            }
            else if (cf && !cs) // 有色走到无色上
            {
                if (um[{t.first.first, t.first.second}] == 0) continue;
                //如果父节点真实颜色是无色，什么都别做
                cost[{a, b}] = min(cost[{a, b}],cost[{t.first.first, t.first.second}] + 2);
                q.push({ { a,b }, 1});
                q.push({ { a,b }, 2});// 两个颜色都放进去
            }
            
        }
    }
    return cost[{m,m}] == 0 ? -1 : cost[{m,m}];
}
int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x >> y >> c;
        um[{x, y}] = c + 1; // 记录下颜色
    }
    cout << bfs(1, 1);
    return 0;
}