//最短路问题上加了一些特殊的限制
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int g[N][N];
bool st[N][N];
int dist[N][N];
int n,m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int ans = 2e9;
void dfs(int x,int y,int lc,int res)
{
if(res > ans)return;//最优性剪枝
if(x == m && y == m)
{
ans = res;
return;
}
if(res >= dist[x][y])return;
dist[x][y] = res;
for(int i = 0; i < 4; i ++)
{
int sx = x + dx[i],sy = y + dy[i],nowc = g[sx][sy];
if(sx <= 0 || sx > m || sy <= 0 || sy > m || st[sx][sy])continue;
st[sx][sy] = true;
if(lc >= 3 && nowc > 0 && nowc < 3)//上次使用了魔法,这次一定不能使用魔法
{
//判断颜色
if((nowc + lc) % 2 == 0)dfs(sx,sy,nowc,res);//颜色相同
else dfs(sx,sy,nowc,res + 1);
}
else if(lc == 1 || lc == 2)//上次没有使用魔法
{
//这次使用魔法变成和上次一样的颜色是代价最小的选择(由于不知道下个格子的颜色)
if(nowc == 0)dfs(sx,sy,lc + 2,res + 2);
//这次不使用魔法
else
{
//判断颜色
if(nowc == lc)dfs(sx,sy,nowc,res);
if(nowc != lc)dfs(sx,sy,nowc,res + 1);
}
}
//回溯
st[sx][sy] = false;
}
}
int main()
{
memset(dist,0x3f,sizeof dist);
cin >> m >> n;//m是棋盘大小,n是颜色格点的数量
for(int i = 0; i < n; i ++)
{
int a,b,c;cin >> a >> b >> c;
g[a][b] = c + 1;
}
st[1][1] = true;
dfs(1,1,g[1][1],0);//当前点的坐标,上一次格点的颜色,当前的代价
if(ans == 2e9)cout << -1 << endl;
else cout << ans << endl;
return 0;
}