#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,c,a[1010][1010]/*存地图*/,ans=INT_MAX;
bool b[1010][1010];//判重
int d[10]={0, 0,0,-1,1, 1,-1,0,0},v[1010][1010];//d方向，v记忆化数组
void dfs(int x,int y,int q){
	for(int i=1;i<=4;i++){
		int nx=x+d[i],ny=y+d[i+4];
		if(nx>m||nx<1||ny>m||ny<1||b[nx][ny]||(a[x][y]!=2||a[nx][ny]!=2)) continue;
		if(nx==m&&ny==m){
			ans=min(ans,q);
			return; 
		}
			
		if(a[nx][ny]==2&&v[nx][ny]>q+2){
			b[nx][ny]=1;v[nx][ny]=q+2;
			a[nx][ny]=a[x][y];
			dfs(nx,ny,q+2);
			a[nx][ny]=2;
			b[nx][ny]=0;
		}
		else if(a[x][y]==a[nx][ny]&&v[nx][ny]>q){
			b[nx][ny]=1;v[nx][ny]=q;
			dfs(nx,ny,q);
			b[nx][ny]=0;
		}
		else if(a[x][y]!=a[nx][ny]&&v[nx][ny]>q+1){
			b[nx][ny]=1;v[nx][ny]=q+1;
			dfs(nx,ny,q+1);
			b[nx][ny]=0;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>m>>n;memset(a,2,sizeof(a));
	memset(v,INT_MAX,sizeof(v));
	memset(b,0,sizeof(b));
	for(int i=1;i<=m;i++){
		cin>>x>>y>>c;
		a[x][y]=c;
	}a[1][1]=1;dfs(1,1,0);
	if(ans==INT_MAX)
		cout<<"-1";
	else cout<<ans;
	return 0;
}