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

const int N=2e5+100;
int n,m,a[101][101];
struct node{
	int x,y,c,cha;
};
int vis[101][101];
int cost[101][101];
int x2[4]={-1,1,0,0};
int y2[4]={0,0,-1,1};

void bfs(){
	queue<node> q;
	node start={1,1,a[1][1],0};
	cost[1][1]=0;
	vis[1][1]=1;
	q.push(start);
	while(!q.empty()){
		node u=q.front();
		q.pop();
		//cout<<u.x<<" "<<u.y<<endl;
		//vis[u.x][u.y]=1;
		for(int i=0;i<4;i++){
			int vx=u.x+x2[i],vy=u.y+y2[i];
			if(vx<1||vx>n||vy<1||vy>n) continue;
			if(!(a[vx][vy]==-1&&u.cha)){
				//cout<<vx<<" "<<vy<<endl;
				if(a[vx][vy]!=u.c&&a[vx][vy]!=-1){
					//cout<<vx<<" "<<vy<<endl;
					cost[vx][vy]=min(cost[u.x][u.y]+1,cost[vx][vy]);
					if(!vis[vx][vy]){
						q.push(node{vx,vy,a[vx][vy],0});
						vis[vx][vy]=1;
					}
				}
				else if(a[vx][vy]==u.c){
					cost[vx][vy]=min(cost[u.x][u.y],cost[vx][vy]);
					//cout<<vx<<" "<<vy<<endl;
					if(!vis[vx][vy]){
						q.push(node{vx,vy,a[vx][vy],0});
						vis[vx][vy]=1;
					}
				}
				else if(a[vx][vy]==-1){
				//	cout<<vx<<" "<<vy<<endl;
					cost[vx][vy]=min(cost[u.x][u.y]+2,cost[vx][vy]);
					if(!vis[vx][vy]){
						q.push(node{vx,vy,a[u.x][u.y],1});
						vis[vx][vy]=1;
					}
				}
			}
		}
		//vis[u.x][u.y]=0;
		//cout<<endl;
	}
}
signed main(){
	memset(a,-1,sizeof(a));
	memset(cost,0x3f3f3f3f,sizeof(cost));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,c;
		cin>>x>>y>>c;
		a[x][y]=c;
	}
	bfs();
	
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout<<cost[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	
	if(vis[n][n]) cout<<cost[n][n];
	else cout<<-1;
}