#include <bits/stdc++.h>
using namespace std;
/*
  左上走到右下
  1、所在位置必须有色
     c=1黄色 c=0红色  
  2、同色移动不需金币
  3、不同色移动花1个
  4、花2个金币变色，魔法不能连用，变色走过恢复
  求最少需要多少金币 
*/
//方向数组 
int fx[4] = {-1,0,1,0};
int fy[4] = {0,-1,0,1};
//存储每个点的最优解 
int f[110][110];
//存储棋盘 
int mp[110][110];
int m,n,ans = INT_MAX;

//深搜
//sum：到x,y最少花多少金币 magic：到该点是否使用魔法 
void dfs(int x,int y,int sum,bool magic){
	//修剪掉3种无效的情况
	//越界 
	if(x < 1 || y < 1 || x > m || y > m) return; 
	if(mp[x][y] == 0) return; //无色区域
	if(sum >= f[x][y]) return;//不是最优解，比最优解大
	
	f[x][y] = sum;
	if(x == m && y == m){
		if(sum < ans) ans = sum;//更新最优解
		return; 
	} 
	
	//尝试4个方向
	for(int i = 0;i < 4;i++){
		int tx = x + fx[i];
		int ty = y + fy[i];
		//如果下一格有色
		if(mp[tx][ty] != 0){
			//同色计算 
			if(mp[tx][ty] == mp[x][y]) dfs(tx,ty,sum,false);
			else dfs(tx,ty,sum+1,false); 
		}else{
			//如果下一格无色
			//如果到本格没有使用魔法 
			if(magic == false){
				mp[tx][ty] = mp[x][y];//使用魔法变为同色
				dfs(tx,ty,sum+2,true);
				mp[tx][ty] = 0;//递归回来，魔法失效 
			} 
		} 
	} 
} 

int main(){
	int i,j,x,y,c;
	cin>>m>>n;
	for(i = 1;i <= m;i++){
		for(j = 1;j <= m;j++) f[i][j] = INT_MAX;
	}
	for(i = 1;i <= n;i++){
		cin>>x>>y>>c;
		//1红色 2黄色 0无色 
		mp[x][y] = c + 1;
	}
	dfs(1,1,0,false);
//	for(i = 1;i <= m;i++){
//		for(j = 1;j <= m;j++){
//			cout<<f[i][j]<<" "; 
//		}
//		cout<<endl;
//	}
	
	cout<<((ans == INT_MAX)?-1:ans)<<endl;	
}