#include<bits/stdc++.h>
using namespace std;
const int M=110,N=1010,INF=0x3f3f3f3f;
int m,n,x,y,c,color[M][M],dp[M][M],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},vis[M][M];
void dfs(int nowx,int nowy,int use,int sum){
	if(nowx==m && nowy==m){
		dp[m][m]=min(dp[m][m],sum);
		return;
	}
	dp[nowx][nowy]=min(dp[nowx][nowy],sum);
	for(int i=0;i<4;i++){
		int u=nowx+dx[i];
		int v=nowy+dy[i];
		if(u>=1 && v>=1 && u<=m && v<=m && !vis[u][v]){
			if(color[u][v]!=-1){
				if(color[u][v]==color[nowx][nowy]){
					vis[u][v]=1;
					dfs(u,v,0,sum);
					vis[u][v]=0;
				}
				else{
					vis[u][v]=1;
					dfs(u,v,0,sum+1);
					vis[u][v]=0; 
				}
			}
			else{
				if(!use){
					vis[u][v]=1;
					color[u][v]=color[nowx][nowy];
					dfs(u,v,1,sum+2);
					vis[u][v]=0;
					color[u][v]=-1;
				}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dp,INF,sizeof(dp));
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			color[i][j]=-1;
		}
	}
	for(int i=1;i<=n;i++){
		cin>>x>>y>>c;
		color[x][y]=c;
	}
	dp[1][1]=0;
	vis[1][1]=1;
	dfs(1,1,0,0);
	if(dp[m][m]!=INF) cout<<dp[m][m];
	else cout<<-1;
	return 0;
}