#include<bits/stdc++.h>
using namespace std;
int m,n,ans=0x3f3f3f3f;
int mp[105][105];
int vis[105][105];
int ne[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
struct node{
	int x,y,c,f,t;
};
queue<node> q;
void bfs(){
	q.push((node){1,1,mp[1][1],0,0});
	vis[1][1]=1;
	while(!q.empty()){
		node fr=q.front();
		q.pop();
		for(int i = 0;i<4;i++){
			int nx=fr.x+ne[i][0],ny=fr.y+ne[i][1];
			if(nx==m&&ny==m){
				if(fr.c==mp[nx][ny]) ans=min(ans,fr.t);
				if(fr.c!=mp[nx][ny]&&mp[nx][ny]!=0) ans=min(ans,fr.t+1);
				if(fr.c!=mp[nx][ny]&&mp[nx][ny]==0&&fr.f==0) ans=min(ans,fr.t+2);
			}
			if(vis[nx][ny]) continue; 
			vis[nx][ny]=1;
			if(fr.c==mp[nx][ny]) q.push((node){nx,ny,mp[nx][ny],0,fr.t});
			else if(fr.c!=mp[nx][ny]&&mp[nx][ny]!=0) q.push((node){nx,ny,mp[nx][ny],0,fr.t+1});
			if(fr.f==0&&mp[nx][ny]==0){
				q.push((node){nx,ny,fr.c,1,fr.t+2});
			}
		}
	}
}
int main(){
	scanf("%d%d",&m,&n);
	memset(mp,0,sizeof(mp));
	for(int i = 1;i<=n;i++){
		int x,y,c; scanf("%d%d%d",&x,&y,&c);
		mp[x][y]=c+1;
	}
	bfs();
	if(ans>100000) ans=-1;
	printf("%d",ans);
}