C++ :

#include <bits/stdc++.h>
using namespace std;
/*
  左上走到右下
  1、所在位置必须有色
     c=1黄色 c=0红色  
  2、同色移动不需金币
  3、不同色移动花1个
  4、花2个金币变色，魔法不能连用，变色走过恢复
  求最少需要多少金币 
*/
//方向数组 
int fx[4] = {-1,0,1,0};
int fy[4] = {0,-1,0,1};
//存储每个点的最优解 
int f[110][110];
//存储棋盘 
int mp[110][110];
int m,n,ans = INT_MAX;

//深搜
//sum：到x,y最少花多少金币 magic：到该点是否使用魔法 
void dfs(int x,int y,int sum,bool magic){
	//修剪掉3种无效的情况
	//越界 
	if(x < 1 || y < 1 || x > m || y > m) return; 
	if(mp[x][y] == 0) return; //无色区域
	if(sum >= f[x][y]) return;//不是最优解，比最优解大
	
	f[x][y] = sum;
	if(x == m && y == m){
		if(sum < ans) ans = sum;//更新最优解
		return; 
	} 
	
	//尝试4个方向
	for(int i = 0;i < 4;i++){
		int tx = x + fx[i];
		int ty = y + fy[i];
		//如果下一格有色
		if(mp[tx][ty] != 0){
			//同色计算 
			if(mp[tx][ty] == mp[x][y]) dfs(tx,ty,sum,false);
			else dfs(tx,ty,sum+1,false); 
		}else{
			//如果下一格无色
			//如果到本格没有使用魔法 
			if(magic == false){
				mp[tx][ty] = mp[x][y];//使用魔法变为同色
				dfs(tx,ty,sum+2,true);
				mp[tx][ty] = 0;//递归回来，魔法失效 
			} 
		} 
	} 
} 

int main(){
	int i,j,x,y,c;
	cin>>m>>n;
	for(i = 1;i <= m;i++){
		for(j = 1;j <= m;j++) f[i][j] = INT_MAX;
	}
	for(i = 1;i <= n;i++){
		cin>>x>>y>>c;
		//1红色 2黄色 0无色 
		mp[x][y] = c + 1;
	}
	dfs(1,1,0,false);
//	for(i = 1;i <= m;i++){
//		for(j = 1;j <= m;j++){
//			cout<<f[i][j]<<" "; 
//		}
//		cout<<endl;
//	}
	
	cout<<((ans == INT_MAX)?-1:ans)<<endl;	
}

Pascal :

var
 n,m,j,k,i,l,x,y,z,max:longint;
 map,ans:array[0..1001,0..1001]of longint;
 f:array[0..1001,0..1001]of boolean;
 aans:array[0..1001,0..1001]of longint;
procedure tt(a,b:longint);
begin
 if map[x+1,y]<>1 then map[x+1,y]:=2;
 if map[x-1,y]<>1 then map[x-1,y]:=2;
 if map[x,y+1]<>1 then map[x,y+1]:=2;
 if map[x,y-1]<>1 then map[x,y-1]:=2;
 map[x,y]:=1;
end;

function check(q,p:longint):boolean;
begin
 if (q>n)or(q<1)or(p>n)or(p<1) then exit(false);
 exit(true);
end;

function find(var q,p:longint):longint;
begin
 if q=2 then begin
              q:=p;
              exit(2);
             end;
 if (p=0) and (q=0) then exit(0);
 if (p=0) and (q=1) then exit(1);
 if (p=1) and (q=0) then exit(1);
 if (p=1) and (q=1) then exit(0);
end;

procedure dfs(dep,a,b,rp:longint);
 var
  k,rrp,aa:longint;
begin
 if (a=n) and (b=n) then begin
                          if max>rp then max:=rp;
                          exit;
                         end;
 if (map[a+1,b]=1) and (f[a+1,b]) and check(a+1,b) then
     begin
      f[a+1,b]:=false;
      k:=ans[a+1,b];
      rrp:=rp;
      aa:=rp+find(ans[a+1,b],ans[a,b]);
      if aa<aans[a+1,b]then
       begin
       aans[a+1,b]:=aa;
       dfs(1,a+1,b,aa);
      end;
      rp:=rrp;
      ans[a+1,b]:=k;
      f[a+1,b]:=true;
     end;
 if (map[a+1,b]=2) and (dep=1) and (f[a+1,b]) and check(a+1,b) then
     begin
      f[a+1,b]:=false;
      k:=ans[a+1,b];
      rrp:=rp;
      aa:=rp+find(ans[a+1,b],ans[a,b]);
      if aa<aans[a+1,b]then
       begin
       aans[a+1,b]:=aa;
       dfs(2,a+1,b,aa);
      end;
      rp:=rrp;
      ans[a+1,b]:=k;
      f[a+1,b]:=true;
     end;
 if (map[a-1,b]=1) and (f[a-1,b]) and check(a-1,b) then
     begin
      f[a-1,b]:=false;
      k:=ans[a-1,b];
      rrp:=rp;
      aa:=rp+find(ans[a-1,b],ans[a,b]);
      if aa<aans[a-1,b]then
       begin
       aans[a-1,b]:=aa;
       dfs(1,a-1,b,aa);
      end;
      rp:=rrp;
      ans[a-1,b]:=k;
      f[a-1,b]:=true;
     end;
 if (map[a-1,b]=2) and (dep=1) and (f[a-1,b]) and check(a-1,b) then
     begin
      f[a-1,b]:=false;
      k:=ans[a-1,b];
      rrp:=rp;
      aa:=rp+find(ans[a-1,b],ans[a,b]);
      if aa<aans[a-1,b]then
       begin
       aans[a-1,b]:=aa;
       dfs(2,a-1,b,aa);
      end;
      rp:=rrp;
      ans[a-1,b]:=k;
      f[a-1,b]:=true;
     end;
 if (map[a,b+1]=1) and (f[a,b+1]) and check(a,b+1) then
     begin
      f[a,b+1]:=false;
      k:=ans[a,b+1];
      rrp:=rp;
      aa:=rp+find(ans[a,b+1],ans[a,b]);
      if aa<aans[a,b+1]then
       begin
       aans[a,b+1]:=aa;
       dfs(1,a,b+1,aa);
      end;
      rp:=rrp;
      ans[a,b+1]:=k;
      f[a,b+1]:=true;
     end;
 if (map[a,b+1]=2) and (dep=1) and (f[a,b+1]) and check(a,b+1) then
     begin
      f[a,b+1]:=false;
      k:=ans[a,b+1];
      rrp:=rp;
      aa:=rp+find(ans[a,b+1],ans[a,b]);
      if aa<aans[a,b+1]then
       begin
       aans[a,b+1]:=aa;
       dfs(2,a,b+1,aa);
      end;
      rp:=rrp;
      ans[a,b+1]:=k;
      f[a,b+1]:=true;
     end;
 if (map[a,b-1]=1) and (f[a,b-1]) and check(a,b-1) then
     begin
      f[a,b-1]:=false;
      k:=ans[a,b-1];
      rrp:=rp;
      aa:=rp+find(ans[a,b-1],ans[a,b]);
      if aa<aans[a,b-1]then
       begin
       aans[a,b-1]:=aa;
       dfs(1,a,b-1,aa);
      end;
      rp:=rrp;
      ans[a,b-1]:=k;
      f[a,b-1]:=true;
     end;
 if (map[a,b-1]=2) and (dep=1) and (f[a,b-1]) and check(a,b-1) then
     begin
      f[a,b-1]:=false;
      k:=ans[a,b-1];
      rrp:=rp;
      aa:=rp+find(ans[a,b-1],ans[a,b]);
      if aa<aans[a,b-1]then
       begin
       aans[a,b-1]:=aa;
       dfs(2,a,b-1,aa);
      end;
      rp:=rrp;
      ans[a,b-1]:=k;
      f[a,b-1]:=true;
     end;
end;
begin
 readln(n,m);
 max:=maxlongint;
 fillchar(f,sizeof(f),true);
 f[1,1]:=false;
 for i:=1 to n do
  for j:=1 to n do
   begin
   ans[i,j]:=2;
   aans[i,j]:=maxlongint;
   end;
 for i:=1 to m do
  begin
   readln(x,y,z);
   ans[x,y]:=z;
   tt(x,y);
  end;
 dfs(1,1,1,0);
 if max<>2147483647 then writeln(max)
                    else writeln('-1');
end.