include

include

include

using namespace std;
int map[105][105],val[105][105];
struct node{
int x,y,c,v;
};
queue<node>q;
int main() {
int m,n,di[4][2]={0,1,1,0,0,-1,-1,0},ans=0x7f7f7f7f;
memset(map,-1,sizeof(map));
memset(val,0x7f,sizeof(val));
cin>>m>>n;
for(int i=0;i<n;i++){
int x,y,c;
cin>>x>>y>>c;
map[x][y]=c;
}
q.push((node){1,1,map[1][1],0});
val[1][1]=0;
while(!q.empty()){
int x=q.front().x,y=q.front().y,c=q.front().c,v=q.front().v;
if(v>ans){
q.pop();
continue;
}
if(x==m&&y==m){
ans=min(ans,v);
q.pop();
continue;
}
for(int k=0;k<4;k++){
int dx=x+di[k][0],dy=y+di[k][1];
if(dx>0&&dy>0&&dx<=m&&dy<=m){
int bc=map[x][y],dc=map[dx][dy],mv=val[dx][dy],dv;
if(dc>=0&&bc>=0){
dv=v+(dc==bc?0:1);
if(mv>dv){
q.push((node){dx,dy,dc,dv});
val[dx][dy]=dv;
}
}else if(dc<0&&bc>=0){
if(mv>v+2){
q.push((node){dx,dy,bc,v+2});
val[dx][dy]=v+2;
}
}else if(dc>=0&&bc<0){
dv=v+(c==dc?0:1);
if(mv>dv){
q.push((node){dx,dy,dc,dv});
val[dx][dy]=dv;
}
}
}
}
q.pop();
}
if(ans==0x7f7f7f7f){
cout<<"-1"<<endl;
}else {
cout<<ans<<endl;
}
return 0;
}</node>