#include <bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int sum=0,a=1;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-'){
			a=-1;
		}
		c=getchar();
	}
	while(c>='0' && c<='9'){
		sum=sum*10+c-'0';
		c=getchar();
	}
	return sum*a;
}
void write(int a){
	if(a<0){
		a*=-1;
		putchar('-');
	}
	if(a>9)
		write(a/10);
	putchar(a%10+'0');
}
int start,en,n,m,x[1001],y[1001],c[1001],s[1001][1001],p[1001],ans[1001];
void Dijkstra(){
	p[start]=true;
	for(int i=1;i<=m;i++){
		ans[i]=s[start][i];
	}
	for(int i=1;i<m;i++){
		int minn=2147483648,a=-1;
		for(int j=1;j<=m;j++){
			if(!p[j] && ans[j]<=minn){
				minn=ans[j];
				a=j;
			}
		}
		if(a==-1)
			break;
		p[a]=true;
		for(int j=1;j<=m;j++){
			ans[j]=min(ans[j],ans[a]+s[a][j]);
		}
	}
}
signed main(){
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			s[i][j]=2147483648;
		}
	}
	bool flag=true;
	for(int i=1;i<=m;i++){
		x[i]=read();
		y[i]=read();
		c[i]=read();
		if(x[i]==1 && y[i]==1){
			start=i;
		}
		else if(x[i]==n && y[i]==n){
			flag=false;
			en=i;
		}
	}
	if(flag){
		en=m+1;
		x[m+1]=n;
		y[m+1]=n;
	}
	for(int i=1;i<m;i++){
		for(int j=i+1;j<=m;j++){
			if(abs(x[i]-x[j])+abs(y[i]-y[j])==1){
				s[i][j]=abs(c[i]-c[j]);
				s[j][i]=abs(c[i]-c[j]);
			}
			else if(abs(x[i]-x[j])+abs(y[i]-y[j])==2){
				s[i][j]=2+abs(c[i]-c[j]);
				s[j][i]=2+abs(c[i]-c[j]);
			}
		}
	}
	if(flag){
		for(int i=1;i<=m;i++){
			if(abs(x[i]-x[en])+abs(y[i]-y[en])==1){
				s[i][en]=2;
				s[en][i]=2;
			}
		}
		m++;
	}
	Dijkstra();
	write(ans[en]==2147483648?-1:ans[en]);
	return 0;
}