#include<bits/stdc++.h>
using namespace std;
long long board[1001][1001];
bool be[1001][1001];
long long walk[9]={0,1,-1,0,0,0,0,1,-1};
long long ans[1001][1001];
long long m,n;
void dfs(long long x,long long y,bool magic,long long money){
	if(ans[x][y]<=money) return;
	else ans[x][y]=money;
	if(x==m&&y==m){
		return;
	}
	be[x][y]=true;
	for(long long i=1;i<=4;i++){
		long long nx=x+walk[i];
		long long ny=y+walk[i+4];
		if(be[nx][ny]==true||(nx>m||ny>m||nx<1||ny<1)) continue;
		//cout<<endl<<x<<" "<<y<<" "<<magic<<" "<<money<<" "<<nx<<" "<<ny;
		if(board[nx][ny]==-1){
			if(magic==true){
				board[nx][ny]=board[x][y];
				dfs(nx,ny,false,money+2);
				board[nx][ny]=-1;
			} 
		}
		else{
			if(board[nx][ny]==board[x][y]){
				dfs(nx,ny,true,money);
				
			}
			else{
				dfs(nx,ny,true,money+1);
			}
		}
	}
	be[x][y]=false;
}
int main(){
	memset(ans,10000,sizeof(ans));
	memset(board,false,sizeof(be));
	cin>>m>>n;
	long long x,y,color;
	for(long long i=1;i<=m;i++){
		for(long long j=1;j<=m;j++){
			board[i][j]=-1;
		}
	}
	for(long long i=1;i<=n;i++){
		cin>>x>>y>>color;
		board[x][y]=color;
	}
	dfs(1,1,true,0);
	if(ans[n][m]==10000){
		cout<<-1;
	}
	else
	cout<<ans[m][m];
	return 0;
}