#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int mx=1005;
int n,m,x,y,c,map[mx][mx],dp[mx][mx];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct point{
	int l,r;
	int colour;
	bool flm;
	int now;
};
queue<point> q;
int main(){
	cin>>m>>n;
	memset(map,-1,sizeof(map));
	for(int i=1;i<=n;i++){
		cin>>x>>y>>c;
		map[x][y]=c;
	}
	memset(dp,0x7f,sizeof(dp));
	int s=dp[m][m];
	point a;
	a.l=1;
	a.r=1;
	a.colour=map[1][1];
	a.flm=1;
	q.push(a);
	dp[1][1]=0;
	while(!q.empty()){
		point p=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int fx=dx[i]+p.l;
			int fy=dy[i]+p.r;
			dp[fx][fy]=p.now;
			if(fx>=1&&fy>=1&&fx<=m&&fy<=m){
				if(map[fx][fy]!=-1&&p.now+abs(p.colour-map[fx][fy])<dp[fx][fy]){
					point b;
					b.l=fx;
					b.r=fy;
					b.colour=map[fx][fy];
					b.flm=1;
					b.now=p.now+abs(p.colour-map[fx][fy]);
					q.push(b);
				}
				if(p.flm==1){
					if(map[fx][fy]==-1&&p.now+2<dp[fx][fy]){
						point b;
						b.l=fx;
						b.r=fy;
						b.colour=p.colour;
						b.flm=0;
						b.now=p.now+2;
						q.push(b);
					}
				}
			}
		}
	}
	if(dp[m][m]==s)cout<<-1;
	else cout<<dp[m][m];
	return 0;
}

完全不知道错在哪里