AC

#include<bits/stdc++.h>
using namespace std;
int inf=0x7fffffff;
int cost[105][105]; //每一个点的最小金币花费
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};   //某一个点向四周运动  
int mapp[105][105];//表示棋盘坐标,数值用于储存颜色值，0代表无色，1代表红色，2代表黄色
int m;
void dfs(int x,int y,int sum,int flag)
{   //深搜，剪枝，递归  flag=1表示本次可以使用魔法，flag=0表示上一次已经使用了魔法，本次无法使用 
	if(x<1||x>m||y<1||y>m) return ;//已经出界
	if(sum>=cost[x][y]) return ;  //此时的金币花费已经大于已经求得的最小值，出界！
 	else cost[x][y] = sum;
	for(int i=0;i<4;i++) //向 上下左右 四个点去搜索
		{
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(mapp[xx][yy]>0) //下一个点有色 
				{
					if(mapp[xx][yy]==mapp[x][y])
						dfs(xx,yy,sum,1); 
					else //颜色不同，花费一个金币 
						dfs(xx,yy,sum+1,1);
				} 
			else  //若下一个点无色
				if(flag==1) // 且本次可以使用魔法 
				{
					mapp[xx][yy]=mapp[x][y]; 
					dfs(xx,yy,sum+2,0);//下一次不能使用魔法 
					mapp[xx][yy]=0;//回溯 
				}		 
		}
} 
int main(){
    int n;
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
		cost[i][j]=inf;      //初始化花费值为inf
	for(int i=1;i<=n;i++)
		{
			int x,y,c;
			cin>>x>>y>>c;
			mapp[x][y]=c+1; //map默认为0 
		}	

	dfs(1,1,0,1);//深搜结束，可以求得从(1,1)点到达任意一个点的最小金币花费
	if(cost[m][m] != inf) cout<<cost[m][m];
	else cout<<-1;
    return 0;
}