#include <bits/stdc++.h>
using namespace std;
int dx[5]={0,0,0,-1,1};
int dy[5]={0,1,-1,0,0};
struct node{
	int x,y,s;
};
queue<node>q;
int i,j,k,n,m,ans,a[101][101],bj[101][101],f[101][101],x,y,c;
inline int read(){
	int sz=0;
	char ss=' ';
	while(ss<'0'||ss>'9')ss=getchar();
	while(ss>='0'&&ss<='9')sz=sz*10+ss-'0',ss=getchar();
	return sz;
}
int main() {
	m=read(),n=read();
	memset(f,0x3f3f3f3f,sizeof(f));
	for(i=1;i<=m;++i)
		for(j=1;j<=m;++j)
			a[i][j]=2;
	for(i=1;i<=n;++i){
		x=read(),y=read(),c=read();
		a[x][y]=c;
		bj[x][y]=1;
	}
	node head;
	head.x=1,head.y=1,head.s=0;
	q.push(head);
	f[1][1]=0;
	while(!q.empty()){
		int xx=q.front().x,yy=q.front().y,color=a[xx][yy];
		for(i=1;i<=4;++i){
			int u=xx+dx[i],v=yy+dy[i],w=0;
			if(u>=1&&u<=m&&v>=1&&v<=m){
				if(!bj[xx][yy]){
					if(a[u][v]==2)continue;
				}
				if(a[u][v]!=color){
					if(a[u][v]<2)w=1;
					else w=2;
				}
				if(!bj[u][v])w=2;
				if(f[u][v]>f[xx][yy]+w){
					node tail;
					tail.x=u,tail.y=v;
					q.push(tail);
					f[u][v]=f[xx][yy]+w;
					if(a[u][v]==2)a[u][v]=color;
					
					//cout<<xx<<' '<<yy<<' '<<u<<' '<<v<<' '<<f[u][v]<<endl;
				}
			}
		}
		if(!bj[xx][yy])a[xx][yy]=2;
		q.pop();
	}
	if(f[m][m]!=0x3f3f3f3f)printf("%d",f[m][m]);
	else printf("-1");
	return 0;
}