#include<bits/stdc++.h>
using namespace std;
const int dx[4]= {1,-1,0, 0};
const int dy[4]= {0, 0,1,-1};
inline int read() {
	int x=0;
	bool f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')f=0;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return f?x:-x;
}
int n,ans;
int b[200][200];
int vis[200][200];
int c[200][200];
struct node {
	int l,r,num;
	bool operator <(node b)const{//const不可丢 
		return num>b.num;
	}
};
priority_queue<node> q;
int main() {
	memset(vis,0x7f,sizeof vis);
	memset(c,-1,sizeof c);
	n=read(),ans=read();
	while(ans--) {
		int x=read(),y=read(),z=read();
		b[x][y]=z+1;
	}
	q.push(node{1,1,0}),vis[1][1]=0;
	while(!q.empty()){
		node d=q.top();
		q.pop();
		//cout<<d.l<<" "<<d.r<<" "<<endl;
		if(d.l==n&&d.r==n){
			printf("%d ",vis[n][n]);
			return 0;
		}
		for(int i=0;i<4;i++){
			int xx=d.l+dx[i],yy=d.r+dy[i];
			if(xx<1||xx>n||yy<1||yy>n)continue;
			c[xx][yy]=b[d.l][d.r];
			if(b[d.l][d.r]==b[xx][yy]){
				if(b[xx][yy]!=0){
					if(vis[xx][yy]>vis[d.l][d.r])vis[xx][yy]=vis[d.l][d.r],q.push(node{xx,yy,vis[xx][yy]});
				}
				continue;
			}
			else{
				if(!b[d.l][d.r]){
					if(c[d.l][d.r]!=b[xx][yy]){
						if(vis[xx][yy]>vis[d.l][d.r]+1){
							vis[xx][yy]=vis[d.l][d.r]+1;
							q.push(node{xx,yy,vis[xx][yy]});
						}
					}
					else{
						if(vis[xx][yy]>vis[d.l][d.r]){
							vis[xx][yy]=vis[d.l][d.r],q.push(node{xx,yy,vis[xx][yy]});
						}
					}
				}
				else if(!b[xx][yy]){
					if(vis[xx][yy]>vis[d.l][d.r]+2){
						vis[xx][yy]=vis[d.l][d.r]+2,q.push(node{xx,yy,vis[xx][yy]});
					}
				}
				else{
					if(vis[xx][yy]>vis[d.l][d.r]+1){
						vis[xx][yy]=vis[d.l][d.r]+1,q.push(node{xx,yy,vis[xx][yy]});
					}
				}
			}
		}
	}
	puts("-1");
	return 0;
}