#include<bits/stdc++.h>
using namespace std;
int m,n,ans=2e9,a[105][105],fx[5]={0,0,1,0,-1},fy[5]={0,1,0,-1,0};
bool cp[105][105];
void DFS(int x,int y,int coin,bool b){
	if(x!=m||y!=m) cp[x][y]=1;
	//cout<<x<<' '<<y<<' '<<coin<<' '<<b<<endl;
	if(x==m&&y==m){
		 ans=min(ans,coin); 
		 return;
	}
	else{
		for(int i=1;i<=4;i++){
			int tx=fx[i]+x;
			int ty=fy[i]+y;
			if(tx>=1&&ty>=1&&tx<=m&&ty<=m&&!cp[tx][ty]&&a[tx][ty]!=0){
				if(a[tx][ty]==a[x][y]){
					if(tx!=m||ty!=m) cp[tx][ty]=1;
					DFS(tx,ty,coin,0);
				} 
				if(a[tx][ty]!=a[x][y]){
					if(tx!=m||ty!=m) cp[tx][ty]=1;
					DFS(tx,ty,coin+1,0);
				}				
			}		 
		}
		for(int i=1;i<=4;i++){
			int tx=fx[i]+x;
			int ty=fy[i]+y;
			if(tx>=1&&ty>=1&&tx<=m&&ty<=m&&!cp[tx][ty]&&a[tx][ty]==0){
				if(a[tx][ty]==0&&b!=1){
					if(tx!=m||ty!=m) cp[tx][ty]=1;
					a[tx][ty]=a[x][y];
					DFS(tx,ty,coin+2,1);
					a[tx][ty]=0;				
				} 				
			}		 
		}		
	}
}
signed main(){
	//freopen("chess.in","r",stdin);
	//freopen("chess.out","w",stdout);	
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int x,y,c;cin>>x>>y>>c;
		a[x][y]=c+1;
	}
	DFS(1,1,0,0);
	if(ans==2e9) cout<<"-1";
	else cout<<ans;
	
}