#include<iostream>
#define NUM 100
#define INF 985
using namespace std;
int m, n, ans = INF;
int a[NUM][NUM] = { 0 }, f[NUM][NUM] = { 0 };
int dx[] = { -1,0,0,1 };
int dy[] = { 0,1,-1,0 };
void dfs(int x, int y, int sum, bool flag) {
	if (x<0 || x>=m || y<0 || y>=m || sum >= f[x][y]) return;
	f[x][y] = sum;
	if (x == m - 1 && y == m - 1) {
		ans = sum;
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = x + dy[i];
		if (a[nx][ny] >= 0) {
			if (a[nx][ny] == a[x][y])
				dfs(nx, ny, sum, 0);
			else
				dfs(nx, ny, sum + 1, 0);
		}
		else{
			if (!flag) {
				a[nx][ny] = a[x][y];
				dfs(nx, ny, sum + 2, 1);
				a[nx][ny] = -1;
			}
		}
	}
}
int main() {
	cin >> m >> n;
	memset(a, -1, sizeof(a));
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		cin >> a[x - 1][y - 1];
	}
	dfs(0, 0, 0, 0);
	cout << (ans == INF) ? -1 : ans;
}