rt

#include <bits/stdc++.h>
using namespace std;
int m,n,ans = 0x3f3f3f3f;
int a[105][105];
int dp[105][105];
bool b[105][105];
int fx[5] = {0,1,0,-1,0};
int fy[5] = {0,0,1,0,-1};
void dfs(int x,int y,int coin,int color){
	if(x == m && y == m){
		ans = min(coin,ans);
		return;
	}
	cout<<x<<" "<<y<<endl; 
	for(int i = 1;i <= 4;i++){
		int tx = x + fx[i];
		int ty = y + fy[i];
		if(tx <= m && tx >= 1 && ty <= m && ty >= 1){
			if(b[tx][ty] == false){
				if(a[x][y] != -1 || a[tx][ty] != -1){
					if(a[tx][ty] == -1){
						if(dp[x][y] > coin+2){
							b[tx][ty] = true;
							a[tx][ty] = color;
							dp[tx][ty] = coin + 2;
							dfs(tx,ty,coin+2,color);
							b[tx][ty] = false;
							a[tx][ty] = -1;
						}
					}
					else{
						if(a[tx][ty] == color && dp[tx][ty] > coin){
							b[tx][ty] = true;
							dp[tx][ty] = coin;
							dfs(tx,ty,coin,color);
							b[tx][ty] = false;
						}
						else if(dp[tx][ty] > coin+1){
								b[tx][ty] = true;
								dp[tx][ty] = coin + 1;
								dfs(tx,ty,coin+1,a[tx][ty]);
								b[tx][ty] = false;
						}
					}
				}
			}
		}
	}
}
int main(){
	memset(a,-1,sizeof(a));
	memset(dp,0x3f,sizeof(dp));
	cin>>m>>n;
	for(int i = 1;i <= n;i++){
		int x,y,c;
		cin>>x>>y>>c;
		a[x][y] = c;
	}
	b[1][1] = true;
	dfs(1,1,0,a[1][1]);
	if(ans == 0x3f3f3f3f)
		ans = -1;
	cout<<ans;
	return 0;
}