#include <bits/stdc++.h>
const int N = 10000, M = 39600;
const int INF = 0x3f3f3f3f;
const int dx[] = {0, 0, -1, 1, 1, 1, -1, -1, 2, 0, -2, 0};
const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1, 0, 2, 0, -2};
int head[N], next[M], ver[M], edge[M];
int vis[N], dis[N], col[N];
int main() {
	int tot, ans, n, m;
	memset(col, -1, sizeof col);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		col[(x - 1) * n + (y - 1)] = z;
	}
	auto add = [&] (int u, int v, int w) {
		ver[tot] = v;
		edge[tot] = w;
		next[tot] = head[u];
		head[u] = tot++;
	};
	auto legal = [&] (int x) {
		return x && x <= n;
	};
	for (int i = 0; i < n * n; i++) {
		for (int j = 0; j < 12; j++) {
			if (!~col[i]) continue;
			int x = i / n + 1 + dx[j];
			int y = i % n + 1 + dy[j];
			if (!legal(x) || !legal(y)) continue;
			int z = (x - 1) * n + (y - 1);
			int k = col[i] != col[z];
			int p = (j >= 4) * 2;
			add(i, z, k + p);
		}
	}
	memset(dis, 0x3f, sizeof dis);
	dis[0] = 0;
	using node = std::pair<int, int>;
	using ctn = std::vector<node>;
	using cmp = std::greater<node>;
	std::priority_queue<node, ctn, cmp> q;
	q.emplace(0, 0);
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = head[u]; i; i = next[i]) {
			int v = ver[i];
			if (vis[v]) continue;
			if (dis[v] <= dis[u] + edge[i]) continue;
			dis[v] = dis[u] + edge[i];
			q.emplace(dis[v], v);
		}
	}
	if (~col[n*n-1]) ans = dis[n*n-1];
	else ans = std::min(dis[n*n-2], dis[n*n-n-1])+2;
	if (ans == INF) ans = -1;
	printf("%d\n", ans);
	return 0;
}