# include <cstdio>
# include <iostream>
# include <cstring>
# include <queue>
using namespace std;
# define inf 0x3f3f3f3f
int m,n;
int path[150][150][2];
int f[150][150];
int ans=inf;
struct node{
int x,y;
};
int movex[4]={0,0,-1,1};
int movey[4]={1,-1,0,0};
inline int inside(int x,int y){
if(x<1||x>n||y<1||y>n) return 0;
return 1;
}
void bfs(){
memset(f,inf,sizeof(f));
queue<node>q;
node temp;
temp.x=1;temp.y =1;
q.push(temp);
f[1][1]=0;
while(q.size()){
temp=q.front();
q.pop();
int x,y,nx,ny;
x=temp.x ,y=temp.y ;
//cout<<x<<" "<<y<<" "<<" "<<f[x][y]<<endl;
if(x==n&&y==n){
ans=f[x][y];
return ;
}
for(int i=0;i<4;++i){
nx=x+movex[i];
ny=y+movey[i];
if(inside(nx,ny)){
if(path[nx][ny][0]==-1){
if(path[x][y][0]==-1) continue;
if(f[nx][ny]>f[x][y]+2){
path[nx][ny][1]=path[x][y][0];
f[nx][ny]=f[x][y]+2;
temp.x=nx; temp.y =ny;
q.push(temp);
}
}
else{
if(path[x][y][1]==path[nx][ny][1]){
if(f[nx][ny]>f[x][y]){
f[nx][ny]=f[x][y];
temp.x=nx; temp.y =ny;
q.push(temp);
}
}
else{
if(f[nx][ny]>f[x][y]+1){
f[nx][ny]=f[x][y]+1;
temp.x=nx; temp.y =ny;
q.push(temp);
}
}
}
}
}
if(path[x][y][0]==-1) path[x][y][1]=-1;
}
}
int main (){
scanf("%d%d",&n,&m);
memset(path,-1,sizeof(path));
for(int i=1;i<=m;++i){
int x,y,col;
scanf("%d%d%d",&x,&y,&col);
path[x][y][0]=path[x][y][1]=col;
}
bfs();
if(ans==inf) cout<<-1;
else cout<<ans;
return 0;
}
by koosi @ 2018-10-11 17:14:01
@[DDFrocket2](/space/show?uid=59142)
by koosi @ 2018-10-11 17:14:09
希望更丰富的展现？使用Markdown
by Lacer @ 2018-10-11 17:15:00
@[koosi](/space/show?uid=58513)
by Lacer @ 2018-10-11 17:15:32