RT

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

//题意简化
//你需要从(1,1)走到(m,m)，你只能走在有颜色的格子中
//并且使得你所花费的代价最小。
//当你站在一个有颜色的格子上的时候，你可以进行如下2种操作：
//1.向上、下、左、右前行。
//2.向左上、左下、右上、右下、向上连跳2格、向下连跳2格、向左连跳2格、向右连跳2格前行。
//如果你使用的是操作2，你将额外付出2点代价。
//在一次操作中，如果你这次操作的起点格子与终点格子颜色不同，你将付出1点代价。

//如果(m,m)没有颜色
//因为魔法不能连续使用，所以只可能从(m,m−1),(m−1,m)转移。
//如果都没有颜色，就不可能到达(m,m)。
//如果任何一个有颜色，相当于(m,m)变化为有颜色的那个格子的颜色，总代价为2。
//如果2个都有颜色，转移总代价都是2，最后做一下比较就可以了。

int n,m,a[105][105],dis[105][105];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

struct node
{
	int x,y,c,step;
};

queue<node> q;

void bfs()
{
	memset(dis,0x3f,sizeof(dis));
	dis[1][1] = 0;
	q.push({1,1,a[1][1],0});
	while(!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		int c = q.front().c;
		int step = q.front().step;
		q.pop();
		
		for(int i=0;i<4;i++)
		{
			int xnew = x + dx[i];
			int ynew = y + dy[i];
			int stepnew;
			if(xnew < 1 || xnew > m || ynew < 1 || ynew > m) continue;
			
			int cnew = a[xnew][ynew];
			if(cnew != 0)
			{
				if(c != cnew) stepnew = step + 1;
				else stepnew = step;
				
				if(dis[xnew][ynew] <= stepnew) continue;
				
				dis[xnew][ynew] = stepnew;
				q.push({xnew,ynew,cnew,stepnew});
			}
			else if(c != 0)
			{
				stepnew = step + 2;
				if(dis[xnew][ynew] <= stepnew) continue;
				
				dis[xnew][ynew] = stepnew;
				q.push({xnew,ynew,c,stepnew});
			}
		}
	}
}

int main()
{
	scanf("%d %d",&m,&n);
	for(int i=1;i<=n;i++)
	{
		int x,y,c;
		scanf("%d %d %d",&x,&y,&c);
		a[x][y] = c + 1;
	}
	
	bfs();
	
	if(dis[m][m] == 0x3f3f3f3f) printf("-1");
	else printf("%d",dis[m][m]);
	return 0;
}