#include<bits/stdc++.h>
using namespace std;
int INF=0x3f;
int n,m,ma[105][105],dis[105][105];
int dx[12]={0,-1,0,1,-2,-1,1,2,-1,0,1,0},
	dy[12]={2,1,1,1,0,0,0,0,-1,-1,-1,-2},
	dv[12]={2,2,0,2,2,0,0,2,2,0,2,2};
struct node{
	int x,y,c,v;
	bool operator <(node b)const{ 
		return v>b.v;
	}
};
void bfs(){
	priority_queue<node> q;
	q.push(node({1,1,ma[1][1],dis[1][1]}));
	node a,nex;
	while(!q.empty()){
		a=q.top();
		q.pop();
		if(dis[a.x][a.y]<a.v){
			continue;
		}
		for(int i=0;i<12;i++){
			nex.x=a.x+dx[i];
			nex.y=a.y+dy[i];
			nex.v=a.v+dv[i];
			if(nex.x<=0||nex.y<=0||nex.x>n||nex.y>n){
				continue;
			}
			nex.c=ma[nex.x][nex.y];
			if(nex.c==0){
				continue;
			}
			if(a.c!=nex.c){
				nex.v=nex.v+1;
			}
			if(dis[nex.x][nex.y]>nex.v){
				dis[nex.x][nex.y]=nex.v;
				q.push(nex);
			}	
		}
	}
}
int main(){
	memset(dis,0x3f,sizeof(dis));
	dis[1][1]=0; 
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,c;
		cin>>x>>y>>c;
		ma[x][y]=c+1;
	} 
	bfs();
	if(ma[n][n]==0){
		int ans=min(dis[n][n-1],dis[n-1][n])+2;
		if(ans>=INF){
			cout<<-1;
		}else{
			cout<<ans;
		}
	}else if(dis[n][n]>=INF){
		cout<<-1;
	}else{
		cout<<dis[n][n];
	}
	return 0;
}