#include <bits/stdc++.h>
using namespace std;
int a[10000][10000];
bool vis[10000][10000];
struct node{
	int x;
	int y;
	int con;
	int s;
	bool f;
};
int n,m,x,y,c;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
queue<node> q;
int main(){
	cin>>m>>n;
	memset(a,-1,sizeof(a));
	for(int i=1;i<=n;i++){
		cin>>x>>y>>c;
		a[x][y]=c;
	}
	node start;
	start.x=1;
	start.y=1;
	start.con=0;
	start.f=true;
	q.push(start);
	vis[1][1]=true;
	int flag=1;
	while(!q.empty()){
		int x=q.front().x;int y=q.front().y;
		if(x==m&&y==m){
			cout<<q.front().con;
			flag=0;
			break;
		}
		for(int i=0;i<4;i++){
			int tx=x+dx[i];
			int ty=y+dy[i];
			if(tx<0||ty<0||tx>m||ty>m||vis[tx][ty]==true||a[tx][ty]==-1&&q.front().f==false){
				continue;
			}else if(a[tx][ty]==-1&&q.front().f==true){
				node g;
				g.x=tx;
				g.y=ty;
				g.con=g.con+2;
				g.s=a[x][y];
				g.f=false;
				q.push(g);
			}else if(q.front().s!=a[tx][ty]){
				node g;
				g.x=tx;
				g.y=ty;
				g.con=g.con+1;
				g.s=a[x][y];
				g.f=true;
				q.push(g);				
			}else{
				node g;
				g.x=tx;
				g.y=ty;
				g.con=g.con;
				g.s=a[x][y];
				g.f=true;
				q.push(g);					
			}
		}
		q.pop();
	}
	if(flag){
		cout<<-1;
	}
}

看来还是我太蒻了