#include<bits/stdc++.h>
using namespace std;

int ma[105][105],mo[105][105];
int m,n,x,y,c;

void dfs(int x,int y,int c,int q,bool m){
	if(x>m||y>m||x<1||y<1) return;
	mo[x][y]=q;
	
	if(ma[x][y]!=-1){
		if(q+abs(c-ma[x+1][y])<mo[x+1][y]) dfs(x+1,y,ma[x+1][y],q+abs(c-ma[x+1][y]),1);
		if(q+abs(c-ma[x-1][y])<mo[x-1][y]) dfs(x-1,y,ma[x-1][y],q+abs(c-ma[x-1][y]),1);
		if(q+abs(c-ma[x][y+1])<mo[x][y+1]) dfs(x,y+1,ma[x][y+1],q+abs(c-ma[x][y+1]),1);
		if(q+abs(c-ma[x][y-1])<mo[x][y-1]) dfs(x,y-1,ma[x][y-1],q+abs(c-ma[x][y-1]),1);
	}
	if(ma[x][y]==1){
		if(m==1){
			if(q+2<mo[x+1][y]) dfs(x+1,y,c,q+2,0);
			if(q+2<mo[x-1][y]) dfs(x-1,y,c,q+2,0);
			if(q+2<mo[x][y+1]) dfs(x,y+1,c,q+2,0);
			if(q+2<mo[x][y-1]) dfs(x,y-1,c,q+2,0);
		}
	}
	
	return;
}

int main(){
	std::ios::sync_with_stdio(0);
	cin>>m>>n;
	for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) ma[i][j]=-1;
	for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) mo[i][j]=0x3f3f3f3f;
	
	for(int i=1;i<=n;i++){
		cin>>x>>y>>c;
		ma[x][y]=c;
	}
	
	dfs(1,1,ma[1][1],0,1);
	
	if(mo[m][m]==0x3f3f3f3f) cout<<"-1"<<endl;
	else cout<<mo[m][m]<<endl;
	
	return 0;
} 

为什么第一个样例会输出-1啊emm