```cpp
const
mo:array[0..4,1..2] of -1..1=
((0,0),
(0,1),
(0,-1),
(-1,0),
(1,0));
var
m,n,i,x,y,c,t:longint;
a:array[1..100,1..100] of longint;
b:array[1..100,1..100] of longint;
dl:array[1..10000,1..4] of longint;
function bfs:longint;
var
head,tail,i,x,y,nx,ny,t:longint;
begin
head:=0;
tail:=1;
dl[1,1]:=1;
dl[1,2]:=1;
dl[1,3]:=0;
dl[1,4]:=0;
b[1,1]:=0;
while head<tail do begin
inc(head);
x:=dl[head,1];
y:=dl[head,2];
//writeln(x,' ',y,' ',dl[head,3]);
if (x=m) and (y=m) then exit(head);
for i:=1 to 4 do begin
nx:=x+mo[i,1];
ny:=y+mo[i,2];
if (nx>0) and (nx<=m) and (ny>0) and (ny<=m) and ((a[nx,ny]<>maxlongint) or (a[x,y]<>maxlongint)) then begin
t:=dl[head,3];
if a[nx,ny]=maxlongint then inc(t,2)
else if (a[x,y]<>a[nx,ny]) and ((a[x,y]<>maxlongint) or (a[x-mo[dl[head,4],1],y-mo[dl[head,4],2]]<>a[nx,ny])) then inc(t);
if b[nx,ny]>t then begin
inc(tail);
b[nx,ny]:=t;
dl[tail,1]:=nx;
dl[tail,2]:=ny;
dl[tail,3]:=t;
dl[tail,4]:=i;
end;
end;
end;
end;
exit(0);
end;
begin
{assign(input,'chess.in');
reset(input);
assign(output,'chess.out');
rewrite(output);}
readln(m,n);
filldword(a,sizeof(a),maxlongint);
filldword(b,sizeof(b),maxlongint);
fillchar(dl,sizeof(dl),0);
for i:=1 to n do begin
readln(x,y,c);
a[x,y]:=c;
end;
writeln;
t:=bfs;
if t=0 then writeln(-1)
else writeln(dl[t,3]);
{close(input);
close(output);}
end.
```
by zdr0820 @ 2017-11-21 20:46:23