#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int m, n, ans;
int a[1005][1005];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool used[1005][1005];
bool flag = true, check;
void dfs(int x, int y, int sum) {
	if (sum >= ans) {
		return ;
	}
	if (x == m && y == m) {
		ans = min(ans, sum);
		check = true;
		return ;
	}
	for (int i = 0; i < 4; i ++) {
		int nx = dir[i][0], ny = dir[i][1];
		if (nx >= 1 && nx <= m && ny >= 1 && ny <= m && !used[nx][ny]) {
			used[nx][ny] = true;
			flag = true; 
			if (a[nx][ny] == a[x][y]) {
				dfs(nx, ny, sum);
			} else if (a[nx][ny] == 0 && a[x][y] == 1 || a[nx][ny] == 1 && a[x][y] == 0) {
				dfs(nx, ny, sum + 1);
			} else if (a[nx][ny] == -1 && flag) {
				a[nx][ny] = a[x][y];
				flag = false;
				dfs(nx, ny, sum + 2);
				flag = true;
				a[nx][ny] = -1;
			}
			used[nx][ny] = false;
		}
	}
}
int main() {
	memset(a, -1, sizeof(a));
	cin >> m >> n;
	for (int i = 1; i <= n; i ++) {
		int u, v, f;
		cin >> u >> v >> f;
		a[u][v] = f;
	}
	used[1][1] = true;
	dfs(1, 1, 0);
	if (check) {
		cout << ans;
	} else {
		cout << -1;
	}
	return 0;
}

不知道自己在干啥
WA5分