#include <iostream>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;

struct node {
	int x, y, color, magic, cost;
	node (int x1, int y1, int color1, int magic1, int cost1) {
		x = x1;
		y = y1;
		color = color1;
		magic = magic1;
		cost = cost1;
	}
};

const int d[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
int m, n, c[110][110], ans = INT_MAX, vis[110][110];

bool pd(int x, int y) {
	return x > 0 && x <= m && y > 0 && y <= m && !vis[x][y];
}

void bfs() {
	queue<node> q;
	q.push(node(1, 1, c[1][1], 0, 0));
	vis[1][1] = 1;
	while(!q.empty()) {
		node f = q.front();
		q.pop();
		int x = f.x, y = f.y;
		if (f.cost > ans) {
			continue;
		}
		if (x == m && y == m) {
			ans = min(ans, f.cost);
			continue;
		}
		for (int i = 0; i < 4; ++i) {
			int xn = x + d[i][0], yn = y + d[i][1];
			if (pd(xn, yn) && (!f.magic || c[xn][yn] > -1)) {
				if (c[xn][yn] == -1) {
					q.push(node(xn, yn, f.color, 1, f.cost + 2));
				} else {
					if (f.color == c[xn][yn]) {
						q.push(node(xn, yn, f.color, 0, f.cost));
					} else {
						q.push(node(xn, yn, c[xn][yn], 0, f.cost + 1));
					}
				}
				vis[xn][yn] = 1;
			}
		}
	}
	if (ans == INT_MAX)
		cout << "-1" << endl;
	else
		cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	memset(c, -1, sizeof c);
	cin >> m >> n;
	for (int i = 1; i <= n; ++i) {
		int x, y;
		cin >> x >> y;
		cin >> c[x][y];
	}
	bfs();
    return 0;
}

码风似乎还行