#include<bits/stdc++.h>
using namespace std;
int m,n,now=-1,cnt=999999;
int a[105][105],vis[105][105];
int xl[10]={0,-1,0,1,0},yl[10]={0,0,-1,0,1};
void dfs(int x,int y,int c,int sum){
	if(x==m&&y==m){
		cnt=min(cnt,sum);
		return;
	}
	for(int i=1;i<=4;i++){
		int xx=x+xl[i];
		int yy=y+yl[i];
		if(xx>=1&&xx<=m&&yy>=1&&yy<=m&&vis[xx][yy]==0){
			if(c!=0) now=-1;
			if(a[xx][yy]==c&&c==0){
				continue;
			}else if(a[xx][yy]==0){
				sum+=2;
				now=c;
			}else if(a[xx][yy]!=c&&now!=c){
				sum++;
			}
			vis[xx][yy]=1;
			dfs(xx,yy,a[xx][yy],sum);
			vis[xx][yy]=0;
		}
	}
	return;
}
int main(){

	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int x,y,c;
		cin>>x>>y>>c;
		a[x][y]=c+1;
	}
	vis[1][1]=1;
	dfs(1,1,a[1][1],0);
	if(cnt==999999) cout<<-1;
	else cout<<cnt;

	return 0;
}