#include <bits/stdc++.h>
using namespace std;
struct node{
	int x,y,c,f;
}q[1000];
int a[1000][1000],n,m,minn=0xffffff;
int xx[4]={-1,1,0,0};
int yy[4]={0,0,1,-1};
bool vis[1000][1000];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int e,b,c;
		cin>>e>>b>>c;
		a[e][b]=c+1;
	}
	q[0].x=1;
	q[0].y=1;
	q[0].c=a[1][1];
	q[0].f=0;
	int front=0,rear=0;
	while(front<=rear){
		if(q[front].f>=minn){
			front++;
			continue;
		}
		if(q[front].x==m&&q[front].y==m){
			minn=min(q[front].f,minn);
			front++;
			continue;
		}
		for(int i=0;i<4;i++){
			int tx=q[front].x+xx[i];
			int ty=q[front].y+yy[i];
			if(tx<=0||tx>m||ty<=0||ty>m||vis[tx][ty]==true)continue;
			if(a[tx][ty]==q[front].c&&a[tx][ty]!=0){
				rear++;
				q[rear].f=q[front].f;
				q[rear].x=tx;
				q[rear].y=ty;
				q[rear].c=a[tx][ty];
				vis[tx][ty]=true;
			}else if(a[tx][ty]!=0){
				rear++;
				q[rear].f=q[front].f+1;
				q[rear].x=tx;
				q[rear].y=ty;
				q[rear].c=a[tx][ty];
				vis[tx][ty]=true;
			}else if(a[q[front].x][q[front].y]!=0){
				rear++;
				q[rear].f=q[front].f+2;
				q[rear].x=tx;
				q[rear].y=ty;
				q[rear].c=a[tx][ty];
				vis[tx][ty]=true;
			}
		}
		front++;
	}
	if(minn==0xffffff)cout<<-1;
	else cout<<minn;
}