#include<bits/stdc++.h>
using namespace std;
struct edge {
	int to, l;
	edge(int x, int y) {
		to = x, l = y;
	}
};
vector<edge> edges[40010];
const int d[14][12] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, m, a[110][110], dist[40010];
vector<int> c[1010];
inline void calc() {
	memset(dist, 255, sizeof(dist));
	int s = a[1][1] * m * m + 1;
	dist[s] = 0;
	c[0].push_back(s);
	for (int i = 0;; i++) {
		int front = 0, rear = c[i].size() - 1;
		while (front <= rear) {
			int x = c[i][front++];
			for (auto y : edges[x]) {
				if (!y.l && dist[y.to] == -1) {
					dist[y.to] = i, c[i].push_back(y.to), ++rear;
				}
			}
		}
		for (auto j : c[i]) {
			for (auto y : edges[j]) {
				if (y.l && dist[y.to] == -1) {
					dist[y.to] = i + 1, c[i + 1].push_back(y.to);
				}
			}
		}
		if (c[i + 1].empty()) {
			break;
		}
	}
	int ans = 1 << 30;
	if (dist[m * m] != -1) {
		ans = min(ans, dist[m * m]);
	}
	if (dist[2 * m * m] != -1) {
		ans = min(ans, dist[2 * m * m]);
	}
	if (ans == 1 << 30) {
		printf("-1");
	} else {
		printf("%d", ans);
	}
}
int main() {
	scanf("%d%d", &m, &n);
	memset(a, 255, sizeof(a));
	for (int i = 1; i <= n; i++) {
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		a[x][y] = c;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= m; j++) {
			for (int k = 0; k < 4; k++) {
				int x = i + d[k][0], y = i + d[k][1];
				if (x > m || x < 1 || y < 1 || y > m) {
					continue;
				}
				int s = (i - 1) * m + j, t = (x - 1) * m + y;
				if (a[i][j] != -1) {
					if (a[x][y] == a[i][j]) {
						edges[a[i][j]*m * m + s].push_back(edge(a[i][j]*m * m + t, 0));
					} else {
						if (a[x][y] != -1) {
							edges[a[i][j]*m * m + s].push_back(edge(a[x][y]*m * m + t, 1));
						} else {
							edges[a[i][j]*m * m + s].push_back(edge((a[i][j] + 2)*m * m + t, 1));
						}
					}
				} else {
					if (a[x][y] != -1) {
						edges[a[x][y]*m * m + s].push_back(edge(a[x][y]*m * m + t, 0));
						edges[(1 - a[i][j])*m * m + s].push_back(edge(a[x][y]*m * m + t, 1));
					}
				}
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == -1) {
				int s = (i - 1) * m + j;
				edges[2 * m * m + s].push_back(edge(s, 1));
				edges[3 * m * m + s].push_back(edge(m * m + s, 1));
			}
		}
	}
	calc();
}

大犇们，帮帮看看哪里错了呗 谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢谢