#include<bits/stdc++.h>
using namespace std;
int m,n,ans=2147483647;
int co[150][150];
int vis[150][150];
struct node{
	int x,y,t,c,i;
	bool flag;
}s,u;
int dx[5]={0,1,0,-1,0},
	dy[5]={0,0,1,0,-1};
queue<node>q;
void bfs(){
	s.x=1;
	s.y=1;
	s.c=co[1][1];
	s.t=0;
	s.flag=0;
	q.push(s);
	while(!q.empty()){
		s=q.front();
		q.pop();
		if(s.x==m&&s.y==m){
			ans=min(ans,s.t);
			continue;
		}
		vis[s.x][s.y]=1;
		for(int i=1;i<=4;i++){
			int xx=s.x+dx[i];
			int yy=s.y+dy[i];
			if(xx<0||xx>m||yy<0||yy>m||vis[xx][yy]==1)continue;
			if(co[xx][yy]==-1&&s.flag==1)continue;
			u.x=xx;
			u.y=yy;
			u.i=i;
			if(co[xx][yy]==s.c){
				u.c=co[xx][yy];
				u.t=s.t;
				u.flag=0;
				q.push(u);
			}
			else if(co[xx][yy]!=-1){
				u.c=co[xx][yy];
				u.t=s.t+1;
				u.flag=0;
				q.push(u);
			}
			else{
				u.c=s.c;
				u.t=s.t+2;
				u.flag=1;
				q.push(u);
			}
		}
	}
}
int main(){
	cin>>m>>n;
	memset(co,-1,sizeof(co));
	for(int x,y,c,i=1;i<=n;i++){
		cin>>x>>y>>c;
		co[x][y]=c;
	}
	bfs();
	if(ans!=2147483647)cout<<ans;
	else cout<<-1;
	return 0;
}