#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 5;
int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while(!('0' <= ch && ch <= '9')) {
		if(ch == '-') f = -f;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = (x << 1) + (x << 3) + ch - '0';
		ch = getchar();
	}
	return x * f;
}
struct node {
	int x , y , color , cost , can;
	node(int a = 0 , int b = 0 , int c = 0 , int d = 0 , int e = 0) : x(a) , y(b) , color(c) , cost(d) , can(e) {}
};
bool pd[N][N];//判定pd[i][j]是否被走过
int mapp[N][N];//地图,有三种情况:当mapp[i][j]为0表示这个格子没有颜色,mapp[i][j]为1表示这个格子是黄的,mapp[i][j]为2表示这个格子是红的
int f[4][2] = { { 0 , 1 } , { 1 , 0 } , { -1 , 0 } , { 0 , -1 } };
int m = 0 , n = 0;
int ans = 1e12;
queue<node> q;
void bfs() {
	pd[1][1] = 1;
	q.push(node(1 , 1 , mapp[1][1] , 0 , 1));
	while(!q.empty()) {	
		if(q.front().x == m && q.front().y == m)
			ans = min(ans , q.front().cost);
		for(int i = 0 ; i < 4 ; i++) {
			int nx = q.front().x + f[i][0];
			int ny = q.front().y + f[i][1];
			if(nx < 1 || ny < 1 || nx > m || ny > m || pd[nx][ny])
				continue;
			int t_can = q.front().can , t_cost = 0 , t_color = mapp[nx][ny];
			int last_color = q.front().color;
			if(t_color == 0) {
				if(q.front().can == 0)
					continue;
				else {
					t_can = 0;
					t_cost = 2;
					t_color = last_color;
				}
			} else {
				t_can = 1;
				if(t_color != last_color)
					t_cost = 1;
			} 
			pd[nx][ny] = 1;
			q.push(node(nx , ny , t_color , q.front().cost + t_cost , t_can));
		}
		q.pop();
	}
}
signed main() {
	m = read() , n = read();//大小:m*m,n个格子有颜色
	for(int i = 1 ; i <= n ; i++) {
		int x = read() , y = read() , w = read();
		if(w == 1) //黄色
			mapp[x][y] = 1;
		else if(w == 0)
			mapp[x][y] = 2;
	}
	bfs();
	if(ans == 1e12)
		cout << -1;
	else
		cout << ans ;
	return 0;
}