#include<bits/stdc++.h> using namespace std; int a[100010][5],t,w,ans=0x3fffffff; int b[110][110],c[110][110]; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};//方向 int main(){ int m,n; cin>>m>>n; memset(c,0x3f,sizeof(c)); for(int i=1;i<=n;i++){ int x,y,c; scanf("%d%d%d",&x,&y,&c); b[x][y]=c+1; } int t=0,w=1; a[1][0]=1,a[1][1]=1,a[1][2]=0,a[1][3]=0; while(t<w){ t++; int x=a[t][0],y=a[t][1]; if(x==m&&y==m) ans=min(ans,a[t][2]); if(c[x][y]<=a[t][2])continue;//花费超过终点或者之前同一个点 if(a[t][2]>ans)continue; c[x][y]=a[t][2];//存一下当前最小 for(int i=0;i<4;i++){ int xx=x+dx[i],yy=y+dy[i]; if(xx<1||yy<1||xx>m||yy>m||(a[t][3]&&!b[xx][yy]))continue;//过界或都没有颜色 w++;//入队 a[w][0]=xx,a[w][1]=yy; if(a[t][3]){ if(a[t][3]!=b[xx][yy])a[w][2]=a[t][2]+1; else a[w][2]=a[t][2]; } else{ if(!b[xx][yy])a[w][2]=a[t][2]+2,a[w][3]=b[x][y]; else if(b[xx][yy]!=b[x][y])a[w][2]=a[t][2]+1; else if(b[xx][yy]==b[x][y])a[w][2]=a[t][2]; } } } if(ans!=0x3fffffff)printf("%d\n",ans);//不能到达终点 else printf("-1\n"); return 0; }