#include<bits/stdc++.h>
using namespace std;
int che[220][220];
int a[220][220];
int w[4][2]= {{0,1},{0,-1},{1,0},{-1,0}};
int m,n,minn=INT_MAX,ans;
bool flag,mag,magi;
void dfs(int x,int y,int c) {
	if(x==m&&y==m) {
		minn=min(ans,minn);
		flag=1;
		return;
	}
	if(x==1&&y==1)ans=0;
	if(ans>minn)return;//剪枝
	for(int i=0; i<4; ++i) {
		int nx=x+w[i][0];
		int ny=y+w[i][1];
		if(nx>=1&&nx<=m&&ny>=1&&ny<=m) {
			if(c!=-1&&che[nx][ny]!=-1&&!a[nx][ny]) {
				ans+=abs(c-che[nx][ny]);
				if(mag) {
					magi=1;
					mag=0;
				}
				a[nx][ny]=1;
				dfs(nx,ny,che[nx][ny]);
				a[nx][ny]=0;
				if(magi) {
					mag=1;
					magi=0;
				}
				ans-=abs(c-che[nx][ny]);
				continue;
			}
			if(c!=-1&&che[nx][ny]==-1&&!mag&&!a[nx][ny]) {
				mag=1;
				ans+=2;
				a[nx][ny]=1;
				dfs(nx,ny,c);
				a[nx][ny]=0;
				ans-=2;
				mag=0;
			}
		} else continue;

	}
	return;
}
int main() {
	//freopen("chess.in","r",stdin);
	//freopen("chess.out","w",stdout);
	cin>>m>>n;
	int x,y,c;
	memset(che,-1,sizeof(che));
	for(int i=1; i<=n; i++) {
		cin>>x>>y>>c;
		che[x][y]=c;
	}
	a[1][1]=1;
	dfs(1,1,che[1][1]);
	if(minn!=INT_MAX)cout<<minn;
	else cout<<-1;
	return 0;
}