#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k, ans=1e9, mp[1005][1005], f[1005][1005];
int dx[]={-1, 0, 1, 0}; 
int dy[]={0, -1, 0, 1};
void dfs(int x, int y, int s, int flag){
	int i, xx, yy;
	if(x<1||y<1||x>n||y>n) return;
	if(x==n&&y==n){
		if(s<ans) ans=s;
		return;
	}
	for(i=0; i<4; i++){
		xx=x+dx[i], yy=y+dy[i];
		if(mp[xx][yy]){
			if(mp[xx][yy]==mp[x][y]){
				dfs(xx, yy, s, 0);
			}
			else{
				dfs(xx, yy, s+1, 0);
			}
		}
		else{
			if(flag==0){
				mp[xx][yy]=mp[x][y];
				dfs(xx, yy, s+2, 1);
				mp[xx][yy]=0;
			}
		}
	}
} 
int main(){
	int a, b, c;
	memset(f, 9, sizeof(f));
	scanf("%d%d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d%d%d", &a, &b, &c);
		mp[a][b]=c+1;
        //黄2 红1 无色0 
	}
	dfs(1, 1, 0, 0);
    //x坐标，y坐标，步数，是否用过魔法
	if(ans!=1e9) printf("%d", ans);
	else printf("-1");
	return 0;
}

MLE了，麻烦各位dalao帮忙找出错误，谢谢