$rt$

#include<stdio.h>
const int dx[]={0,0,0,1,-1},dy[]={0,1,-1,0,0};
int m,n,x,y,c,ans=0x7fffffff;
int map[101][101];
int f[101][101];
bool p[101][101];
int min(int a,int b){if(a<b)return a;return b;}
void dfs(int x,int y,int cnt,int color){
	if(x==m&&y==m){ans=min(ans,cnt);return;}
	for(int i=1;i<=4;i++){
		int X=x+dx[i],Y=y+dy[i];
		if(X<1||X>m||Y<1||Y>m) continue;
		if(p[X][Y]) continue;
		if(map[X][Y]||map[x][y]){
    		if(map[X][Y]==0){
    			if(cnt+2<f[X][Y]){
					p[X][Y]=1;
					f[X][Y]=cnt+2;
					dfs(X,Y,cnt+2,color);
					p[X][Y]=0;
				}
			}
			else{
				if(color==map[X][Y]&&cnt<f[X][Y]){
					p[X][Y]=1;
					f[X][Y]=cnt;
					dfs(X,Y,cnt,color);
					p[X][Y]=0;
				}
				else if(cnt+1<ans&&cnt+1<f[X][Y]){
					p[X][Y]=1;
					f[X][Y]=cnt+1;
					dfs(X,Y,cnt+1,f[X][Y]);
					p[X][Y]=0;
				}
			}
		}
	}
}
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) f[i][j]=0x7fffffff;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&c);
		map[x][y]=c+1;
	}
	p[1][1]=true;
	dfs(1,1,0,map[1][1]);
	/*
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			printf("%2d",map[i][j]);
		}
		putchar(10);
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++)
		    printf("%11d",f[i][j]);
		printf("\n");
	}*/	
	if(ans!=0x7fffffff) return printf("%d",ans-1),0;
	return printf("-1"),0;
}