#include<bits/stdc++.h>
using namespace std;
const int oo=999999999;
int n,m;
int d[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
int a[1005][1005];
int vis[1005][1005];
bool in(int x,int y){
	return x>=1&&x<=m&&y>=1&&y<=m;
}
void dfs(int x,int y,int z,int fg){
	if(vis[x][y]>=vis[m][m]) return;
	for(int i=0;i<4;i++){
		int nx=x+d[i][0];
		int ny=y+d[i][1];
		if(in(nx,ny)==0) continue;
//		if(a[nx][ny]==-1&&fg==1) continue;
		if(a[nx][ny]==-1&&fg==0&&vis[nx][ny]>vis[x][y]+2){
			vis[nx][ny]=vis[x][y]+2;
			dfs(nx,ny,z,1);
		}
		else if(a[nx][ny]==z&&vis[nx][ny]>vis[x][y]){
			vis[nx][ny]=vis[x][y];
			dfs(nx,ny,z,0);
		}
		else if(a[nx][ny]!=-1&&a[nx][ny]!=z&&vis[nx][ny]>vis[x][y]+1){
			vis[nx][ny]=vis[x][y]+1;
			dfs(nx,ny,a[nx][ny],0);
		}
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++)
		{
			a[i][j]=-1;
			vis[i][j]=oo;
		}
	}
	for(int i=0;i<n;i++){
		int x,y,c;
		cin>>x>>y>>c;
		a[x][y]=c;
	}
	vis[1][1]=0;
	dfs(1,1,a[1][1],0);][m]<<endl;
	else cout<<-1<<endl;
	return 0;
}