#include<bits/stdc++.h>
using namespace std;
const int M=109;
const int INF=1e9;
int gra[M][M],n,m,ans=INF;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int v[M][M];
bool vst[M][M];
void dfs(int prex,int prey,int x,int y,int cnt,int isg){
	if(x==m&&y==m){
		v[x][y]=min(v[x][y],cnt),ans=v[x][y];
		return;
	}
	if(cnt>=ans) return;
	vst[x][y]=1;
	v[x][y]=min(v[x][y],cnt);
	for(int k=0;k<4;k++){
		int nx=x+dx[k],ny=y+dy[k];
		if(nx<1||nx>m||ny<1||ny>m||vst[nx][ny]==1) continue;
		if(gra[nx][ny]==0){
			if(isg==1) continue;
			dfs(x,y,nx,ny,cnt+2,1);
		}
		if(gra[nx][ny]==1&&gra[x][y]==1) dfs(x,y,nx,ny,cnt,0);
		else if(gra[nx][ny]==2&&gra[x][y]==2) dfs(x,y,nx,ny,cnt,0);
		else if(gra[nx][ny]==1&&gra[x][y]==2) dfs(x,y,nx,ny,cnt+1,0);
		else if(gra[nx][ny]==1&&gra[x][y]==0){
			if(gra[prex][prey]==1) dfs(x,y,nx,ny,cnt,0);
			else dfs(x,y,nx,ny,cnt+1,0);
		}
		else if(gra[nx][ny]==2&&gra[x][y]==1) dfs(x,y,nx,ny,cnt+1,0);
		else if(gra[nx][ny]==2&&gra[x][y]==0){
			if(gra[prex][prey]==2) dfs(x,y,nx,ny,cnt,0);
			else dfs(x,y,nx,ny,cnt+1,0);
		}
	}
	vst[x][y]=0;
}
int main(){
	//freopen("chess.in","r",stdin);
	//freopen("chess.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int x,y,val;
		cin>>x>>y>>val;
		gra[x][y]=val+1;
	}
	for(int i=0;i<M;i++)
	    for(int j=0;j<M;j++)
	        v[i][j]=INF;
	dfs(0,1,1,1,0,0);
	if(v[m][m]==INF) cout<<"-1";
	else cout<<v[m][m];
	return 0;
}