#include<bits/stdc++.h>
using namespace std;
int ans,minn=1e9,vis[101][101];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int m,n,a[101][101];
int p[101][101];
void dfs(int x,int y,int ys,int q){
	if(x==m&&y==m){
		minn=min(minn,q);
		return;
	}
	for(int i=0;i<4;i++){
		int xx=dx[i]+x;
		int yy=dy[i]+y;
			if(xx>=1&&xx<=m&&yy>=1&&yy<=m){
				if(vis[xx][yy]==0){
					if(a[xx][yy]!=-1||ys!=-1){
			if(a[xx][yy]==-1){
			if(q+2<p[xx][yy]){
			vis[xx][yy]=1;
			p[xx][yy]=q+2;
			dfs(xx,yy,ys,q+2);
			vis[xx][yy]=0;				
			}
		}
		else{
			if(a[xx][yy]!=ys&&q+1<minn){
			vis[xx][yy]=1;
			p[xx][yy]=q+1;
			dfs(xx,yy,a[xx][yy],q+1);
			vis[xx][yy]=0;
			}
		else if(a[xx][yy]==ys&&q<p[xx][yy]){
			vis[xx][yy]=1;
			p[xx][yy]=q;
			dfs(xx,yy,a[xx][yy],q);
			vis[xx][yy]=0;	
			}
		}		
				}
			}
		}
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=-1;
			p[i][j]=1e9;
		}
	}
	for(int i=1;i<=n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=z;
	}
	vis[1][1]=1;
	dfs(1,1,a[1][1],0);
	if(minn==1e9){
	cout<<"-1";
	return 0;
	}
	else
	cout<<minn;
return 0;
}

/*
4 7
1 1 0
1 3 1
2 4 0
3 2 0
3 4 0
4 2 1
4 3 1
*/