#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];
void dfs(int x,int y,int q){
	if(x==m&&y==m){
		ans=min(ans,q);
		return ;
	}
	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]) continue;
		
		if(a[x][y]||a[nx][ny]){
			if(!a[nx][ny]){
				if(q+2<v[ny][ny]){
					b[nx][ny]=1;
					v[nx][ny]=q+2;
					a[nx][ny]=a[x][y];
					dfs(nx,ny,q+2);
					b[nx][ny]=1;
					a[nx][ny]=0;
				}
				cout<<1;
			}
			else{
				if(a[x][y]==a[nx][ny]&&q<v[nx][ny]){
					b[nx][ny]=1;
					v[nx][ny]=q;
					dfs(nx,ny,q);
					b[nx][ny]=0;cout<<2;
				}
				else{
					if(q+1<v[nx][ny]){
						b[nx][ny]=1;
						v[nx][ny]=q+1;
						dfs(nx,ny,q+1);
						b[nx][ny]=0;cout<<3;
					}
				}
			}	
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>m>>n;
	memset(a,0,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+1;
	}b[1][1]=1;dfs(1,1,0);
	if(ans==INT_MAX)
		cout<<"-1";
	else cout<<ans;
	return 0;
}