RT

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#define maxn 110
#define maxny 2010
using namespace std;
int a[maxn][maxn]; //存图
int m, n;
bool book[maxn][maxn]; //判断是否到达

//int visit[maxn][maxn];
int coin[maxn][maxn] = {0}; //存硬币数量

int _next[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct node {
	int x;
	int y;
	int color;
	bool ifuse = false;
};
queue<node> q;
int mi = 100000009;
int col[3] = {1, 0, 2}; //无色代表什么都没有，其余的对应相反的颜色
bool ranse[maxn][maxn]  = {false};
void bfs() {
//	cout << "ok" << endl;
	int zx, zy, tx, ty, color;
	while (!q.empty()) {
		node z = q.front();
		q.pop();
		zx = z.x;
		zy = z.y;
		color = z.color;
		if (zx == m && zy == m) {
			mi = min(mi, coin[zx][zy]);
			return;
		}
		if (ranse[zx][zy] == true) {
			ranse[zx][zy] = false;
		}
//		cout << "ok1" << endl;
		for (int i = 0; i < 4; i ++) {
			tx = zx + _next[i][0];
			ty = zy + _next[i][1];
//			cout << tx << ' ' << ty << endl;
			if (tx < 1 || tx > m || ty < 1 || ty > m) {
//				cout << "NO" << endl;
				continue;
			}
			if (book[tx][ty] == true) {
//				cout << "NO1" << endl;
				continue;
			}
			if (a[tx][ty] == color) { //第一种可能，颜色相同，此时直接入队即可
				book[tx][ty] = true;
				if (z.ifuse == true) {
					z.ifuse = false;
				}
				q.push((node) {
					tx, ty, color, z.ifuse
				});
				coin[tx][ty] = coin[zx][zy];
			}
			if (a[tx][ty] == col[color]) { //第二种可能，有颜色但是颜色相反，所以要加上
				book[tx][ty] = true;
				if (z.ifuse == true) {
					z.ifuse = false;
				}
				q.push((node) {
					tx, ty, col[color], z.ifuse
				});
				coin[tx][ty] = coin[zx][zy] + 1;
			}
			if (a[tx][ty] == 2 && z.ifuse == false) { //第三种可能，无色格子，此时如果有就试试走
				book[tx][ty] = true;
				q.push((node) {
					tx, ty, color, true
				});
				coin[tx][ty] = coin[zx][zy] + 2;
				ranse[tx][ty] = true;
			}
			// 全没有就跳过
//			cout << "ok2" << endl;
		}
	}
	return;
}

int main() {
	//预处理：观察起点是否为无色
	cin >> m >> n;
	//初始化
	memset(book, false, sizeof(book));
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= m; j++) {
			a[i][j] = 2;
//			book[i][j] = false;
		}
	}
	int x, y, color;
	for (int i = 0; i < n; i++) {
		cin >> x >> y >> color;
		a[x][y] = color;
	}
	q.push((node) {
		1, 1, a[1][1]
	});
	bfs();
	if (mi == 100000009) {
		cout << -1;
	} else {
		cout << mi;
	}
	return 0;
}