#include <stdio.h>
#include <cstring>
#define ll long long
using namespace std;

int read(){
	int a1=0,k1=1;char c1=getchar();
	while(c1<'0'||c1>'9'){
		if(c1=='-')k1=-1;c1=getchar();
	}
	while(c1>='0'&&c1<='9'){
		a1=a1*10+c1-'0';
		c1=getchar();
	}
	return a1*k1;
}
inline void out1(ll n) {
	if(n < 0)
		putchar ('-') , n = -n;
	if(n > 9)
		out1(n / 10);
	putchar(n % 10 + '0');
}
inline void out(ll n){
	out1(n);printf("\n");
}
int m,n,ans=0x3f3f3f3f;
int a[102][102],f[102][102];
bool vis[102][102];
int dx[8]={0,1,0,-1,0};
int dy[8]={0,0,1,0,-1};
void dfs(int x,int y,int k,int last){
	if(x<1||x>m||y<1||y>m)return ;
	if(k>ans)return ;
	if(vis[x][y])return ;
	if(k>f[x][y])return ;
	f[x][y]=k;
	if(x==m&&y==m){
		if(k<ans)ans=k;
		f[x][y]=ans;
		return ;
	}
//	printf("%d %d\n",x,y);
	vis[x][y]=true;
	for(int i=1;i<=4;++i){
		int x1=x+dx[i],y1=y+dy[i];
		if(a[x1][y1]!=0){
			if(a[x1][y1]==a[x][y])dfs(x1,y1,k,0);
			else dfs(x1,y1,k+1,0);
		}
//		else ;
		else {
			if(last==0){
				a[x1][y1]=a[x][y];
				dfs(x1,y1,k+2,1);
				a[x1][y1]=0;
			}
		}
	}
	vis[x][y]=false;
//	return f[x][y];
}
int/*signed*/ main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	m=read();n=read();
	int x,y,c;
	for(int i=1;i<=n;++i){
		x=read();y=read();c=read();
		a[x][y]=c+1;
	}
	memset(f,0x7f7f7f,sizeof f);
	dfs(1,1,0,0);
	if(ans!=0x3f3f3f3f){
		printf("%d\n",ans);
	}
	else {
		printf("-1\n");
	}
	return 0;
}

70分提交记录