难受啊，TLE70

#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define pre(i, a, b) for(int i = (a); i >= (b); i--)
#define Ede(i, u) for(int i = h[u]; i; i = ne[i])
#define go(i, a) for(auto i : a)
//#define int long long
#define uint unsigned int
#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define PIL pair<int, LL>
#define PLI pair<LL, int>
#define PLL pair<LL, LL>
#define mp make_pair
#define eb emplace_back
#define opb pop_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sf scanf
#define prf printf
#define el putchar('\n')
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define mmc(arr1, arr2) memcpy(arr1, arr2, sizeof(arr2))
#define Db(x) prf("test(%s): ", x)
const int inf = 0x3f3f3f3f;

template <typename T> inline void rd(T &x){
	x = 0; bool f = true; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();}
	while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
	if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}

using namespace std;

const int N = 110;
int g[N][N];
int n, m;
int ans = inf;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool vis[N][N];
int dist[N][N];
void dfs(int x, int y, int sum, int s){
	if(sum >= ans) return;
	if(x == n && y == n){
		ans = min(ans, sum);
		return;
	}
	if(s == g[x][y]){
		rep(i, 0, 3){
			int tx = x + dx[i], ty = y + dy[i];
			if(tx >= 1 && tx <= n && ty >= 1 && ty <= n && !vis[tx][ty]){
				if(g[tx][ty]){
					if(dist[tx][ty] > sum + ((s == g[tx][ty]) ? 0 : 1)){
						vis[tx][ty] = true;
						dfs(tx, ty, sum + ((s == g[tx][ty]) ? 0 : 1), g[tx][ty]);
						vis[tx][ty] = false;	
					}
				}else if(dist[tx][ty] > sum + 2){
					vis[tx][ty] = true;
					dfs(tx, ty, sum + 2, s);
					vis[tx][ty] = false;
				}
			}
		}
	}else{
		rep(i, 0, 3){
			int tx = x + dx[i], ty = y + dy[i];
			if(tx >= 1 && tx <= n && ty >= 1 && ty <= n && !vis[tx][ty] && g[tx][ty]){
				if(dist[tx][ty] > sum + ((s == g[tx][ty]) ? 0 : 1)){
					vis[tx][ty] = true;
					dfs(tx, ty, sum + ((s == g[tx][ty]) ? 0 : 1), g[tx][ty]);
					vis[tx][ty] = false;	
				}
			}
		}
	}
}

int main(){
	/*
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	*/
	rd(n, m);
	rep(i, 1, m){
		int x, y, c; rd(x, y, c);
		g[x][y] = c ? c : 2;
	}
	mms(dist, 0x3f);
	vis[1][1] = true, dist[1][1] = 0;
	dfs(1, 1, 0, g[1][1]); 
	prf("%d\n", ((ans == inf) ? -1 : ans));
	return 0;
}