RT

#include <cstdio>
#include <queue>
using namespace std;
int m,n,x,y,c;
int col[101][101],mon[101][101];
const int udlr[2][4]={{-1,1,0,0},{0,0,-1,1}}; 
queue <int> qx,qy,quse,qcol;
int main(){
	scanf("%d%d",&m,&n);
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&x,&y,&c);
		col[x][y]=c+1;
	}
	for(int i=0;i<101;i++){
		for(int j=0;j<101;j++){
			mon[i][j]=10000000;
		}
	}
	mon[1][1]=0;
	qx.push(1);qy.push(1);quse.push(0);
	while(!qx.empty()){
		x=qx.front();y=qy.front();c=quse.front();
		qx.pop();qy.pop();quse.pop();
		if(c==1){
			col[x][y]=qcol.front();
			qcol.pop();
		}
		for(int i=0;i<4;i++){
			if(x+udlr[0][i]>0&&x+udlr[0][i]<=m){
				if(y+udlr[1][i]>0&&y+udlr[1][i]<=m){
						if(c==0||col[x+udlr[0][i]][y+udlr[1][i]]!=0){
							if(col[x+udlr[0][i]][y+udlr[1][i]]==col[x][y]){
								if(mon[x][y]<mon[x+udlr[0][i]][y+udlr[1][i]]){
									mon[x+udlr[0][i]][y+udlr[1][i]]=mon[x][y];
									qx.push(x+udlr[0][i]);qy.push(y+udlr[1][i]);quse.push(0);
								}
							}
							else{
								if(col[x+udlr[0][i]][y+udlr[1][i]]!=0){
									if((mon[x][y]+1)<mon[x+udlr[0][i]][y+udlr[1][i]]){
										mon[x+udlr[0][i]][y+udlr[1][i]]=(mon[x][y]+1);
										qx.push(x+udlr[0][i]);qy.push(y+udlr[1][i]);quse.push(0);
									}
								}
								else{
									if((mon[x][y]+2)<mon[x+udlr[0][i]][y+udlr[1][i]]){
										mon[x+udlr[0][i]][y+udlr[1][i]]=(mon[x][y]+2);qcol.push(col[x][y]);
										qx.push(x+udlr[0][i]);qy.push(y+udlr[1][i]);quse.push(1);
									}
								}
							}
						}
				}
			}
		}
		if(c==1){
			col[x][y]=0;
		}
	}
	if(mon[m][m]==10000000){
		printf("-1");
	}
	else{
		printf("%d",mon[m][m]);
	}
	return 0;
}