#include<bits/stdc++.h>
using namespace std;
int m,n;
int x,y,c,col[1100][1100];
int rx[]={0,0,1,-1};
int ry[]={1,-1,0,0};
int nx,ny,minn=0x7fffffff;
bool book[1010][1010];
int mmin[1100][1100];//记录到这个格子最小需要多少钱 
void dfs(int x,int y,int c,int color){
	cout<<x<<" "<<y<<" "<<c<<" "<<color<<endl;
	if(x==m&&y==m){
		minn=min(minn,c);
		return ;
	}
	for(int i=0;i<4;i++){
		nx=x+rx[i];
		ny=y+ry[i];
		bool t=(nx>=1&&nx<=m&&ny>=1&&ny<=m);
		if(t&&!book[nx][ny])
		if(col[x][y]||col[nx][ny]){
			if(col[nx][ny]==0){
				if(c+2<mmin[nx][ny]){
					book[nx][ny]=1;
					mmin[nx][ny]=c+2;
					dfs(nx,ny,c+2,color);
					book[nx][ny]=0;
				}
			}
			else{
				if(color==col[nx][ny]&&c<mmin[nx][ny]){
					book[nx][ny]=1;
					mmin[nx][ny]=c;
					dfs(nx,ny,c,color);
					book[nx][ny]=0;
				}
				else if(c+1<mmin[nx][ny]&&c+1<minn){
					book[nx][ny]=1;
					mmin[nx][ny]=c+1;
					dfs(nx,ny,c+1,col[nx][ny]);
					book[nx][ny]=0;
				}
			}
		}
	}
	
}
int main(){
	cin >> m >> n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			col[i][j]=0;
			book[i][j]=0;
			mmin[i][j]=0x7fffffff;
		}
	}
	//1红色 2黄色 0无色 
	while(n--){
		cin >> x >> y >> c;
		col[x][y]=c+1;
	}
	book[1][1]=1;
	dfs(1,1,0,col[1][1]);
	if(minn==0x7fffffff) cout << -1;
	else cout << minn << endl;
	return 0;
}