#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[10000][10000],g[10000][10000];
bool vis[10000][10000];
void dfs(int x,int y,int con,int s,bool f){
	if(x<1||y<1||x>m||y>m||a[x][y]==-1&&f==true||vis[x][y]==true||g[x][y]<con){
		return;
	}else if(a[x][y]==-1&&f!=true){
		g[x][y]=con;
		vis[x][y]=true;
		dfs(x+1,y,con+2,s,true);
		dfs(x-1,y,con+2,s,true);
		dfs(x,y+1,con+2,s,true);
		dfs(x,y-1,con+2,s,true);
		vis[x][y]=false;
	}else if(a[x][y]!=s){
		g[x][y]=con;
		vis[x][y]=true;
		dfs(x+1,y,con+1,a[x][y],false);
		dfs(x-1,y,con+1,a[x][y],false);
		dfs(x,y+1,con+1,a[x][y],false);
		dfs(x,y-1,con+1,a[x][y],false);	
		vis[x][y]=false;	
	}else{
		g[x][y]=con;
		vis[x][y]=true;
		dfs(x+1,y,con,a[x][y],false);
		dfs(x-1,y,con,a[x][y],false);
		dfs(x,y+1,con,a[x][y],false);
		dfs(x,y-1,con,a[x][y],false);	
		vis[x][y]=false;	
	}
}
int main(){
	cin>>m>>n;
	memset(a,-1,sizeof(a));
	for(int i=1;i<=n;i++){
		int b,c,d;
		cin>>b>>c>>d;
		a[b][c]=d;
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			g[i][j]=0xfff;
		}
	}
	dfs(1,1,0,-1,false);
	if(g[m][m]=0xfff){
		cout<<-1;
	}else{
		cout<<g[m][m];
	}
	return 0;
}

我不太希望再改方法了（除非这种方法怎么剪枝都不能AC）