代码如下：

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

struct Unsigned{
	int Color,Num;
}Map[110][110];
int NextX[4],NextY[4];
bool Visited[12110];
int Dis[12110],N,M;

struct EDGE{
	int Next,To,Dis;
}E[12110];
int Head[12110],Size; 

void Made(void){
	NextX[1]=1;NextY[1]=0;
	NextX[2]=-1;NextY[2]=0;
	NextX[3]=0;NextY[3]=1;
	NextX[4]=0;NextY[4]=-1;
	return;
}

void EDGE_Add(int From,int To,int Dis){
	E[++Size].Next=Head[From];
	E[Size].Dis=Dis;
	Head[From]=Size;
	E[Size].To=To;
	return;
}

bool Judge(int X,int Y){
	if(X<1||X>N)return true;
	if(Y<1||Y>N)return true;
	return false;
}

void Add(int FromX,int FromY){
	if(Map[FromX][FromY].Color==0)
		return;
	for(register int i=1;i<=4;i++){
		int ToX=FromX+NextX[i];
		int ToY=FromY+NextY[i];
		if(Judge(ToX,ToY)==true)
			continue;
		if(Map[ToX][ToY].Color>0){
			if(Map[ToX][ToY].Color==Map[FromX][FromY].Color)
				EDGE_Add(Map[FromX][FromY].Num,Map[ToX][ToY].Num,0);
			if(Map[ToX][ToY].Color!=Map[FromX][FromY].Color)
				EDGE_Add(Map[FromX][FromY].Num,Map[ToX][ToY].Num,1);
			continue;
		}
		for(register int j=1;j<=4;j++){
			int GoX=ToX+NextX[j];
			int GoY=ToY+NextY[j];
			if(GoX==FromX&&GoY==FromY)
				continue;
			if(Judge(GoX,GoY)==true)
				continue;
			if(Map[GoX][GoY].Color==0)
				continue;
			if(Map[GoX][GoY].Color==Map[FromX][FromY].Color)
				EDGE_Add(Map[FromX][FromY].Num,Map[GoX][GoY].Num,2);
			if(Map[GoX][GoY].Color!=Map[FromX][FromY].Color)
				EDGE_Add(Map[FromX][FromY].Num,Map[GoX][GoY].Num,3);
		}
	}
	return;
}

struct Priority{
	int Data,Dis;
	friend bool operator <(Priority Num1,Priority Num2){
		Num1.Dis>Num2.Dis;
	}
};

#define INF 1<<29//跑最短路 
void Dijkstra(void){
	priority_queue <Priority> Queue;
	for(register int i=1;i<=Map[N][N].Num;i++)
		Visited[i]=false,Dis[i]=INF;
	//初始化所有点都未访问过 
	Dis[Map[1][1].Num]=0;//起点设置 
	Queue.push((Priority){Map[1][1].Num,0});
	while(!Queue.empty()){
		Priority Beg=Queue.top();
		Queue.pop();
		int From=Beg.Data;
		if(Visited[From]==true)
			continue;
		Visited[From]=true;
		for(register int i=Head[From];i;i=E[i].Next){
			int To=E[i].To;
			if(Dis[To]>Dis[From]+E[i].Dis){
				Dis[To]=Dis[From]+E[i].Dis;
				if(Visited[To]==false){
					Queue.push((Priority){To,Dis[To]});
				}
			}
		}
	}
	return;
}

int main(void){
	cin>>N>>M;
	for(register int i=1;i<=N+1;i++){
		for(register int j=1;j<=N+1;j++){
			if(j==1)Map[i][j].Num=Map[i-1][N].Num+1;
			else Map[i][j].Num=Map[i][j-1].Num+1;
		}
	}//给二维表上的每一个点标号 
	for(register int i=1;i<=M;i++){
		int X,Y,Z;
		cin>>X>>Y>>Z;Z++;
		Map[X][Y].Color=Z;
	}//给二维表染色 
	Made();//四个方向 
	N++;
	Map[N-1][N].Color=1;
	Map[N][N-1].Color=2;
	for(register int i=1;i<=N;i++)
		for(register int j=1;j<=N;j++)
			Add(i,j);//建图 
	Dijkstra();//跑一遍最短路
	int Min=min(Dis[Map[N][N-1].Num],Dis[Map[N-1][N].Num]);
	if(Min==INF)
		cout<<"-1"<<endl;//如果无法到达，输出-1 
	else cout<<Min<<endl;//如果可以到达，输出答案 
	return 0;
}