#include<bits/stdc++.h>
using namespace std;
const int dx[]={0,-1,1,0,0};
const int dy[]={0,0,0,-1,1};
long long m,a[101][101],n,ans=INT_MAX;
long long c[101][101];
bool b[101][101];
void dfs(int x,int y,long long tool,bool t){
	if(x==m&&y==m){
		ans=min(ans,tool);
		return ;
	}
	else
		for(int i=1;i<=4;i++){
			int xx=x+dx[i];int yy=y+dy[i];
			if(xx>0&&xx<=m&&yy>0&&yy<=m&&!b[xx][yy]){
				if(a[xx][yy]||a[x][y]){
					if(a[x][y]==a[xx][yy]&&tool<c[xx][yy]){
						b[xx][yy]=1;
						c[x][y]=tool;
						dfs(xx,yy,tool,1);
						b[xx][yy]=0;
					}
					else if(tool+1<c[xx][yy]){
						b[xx][yy]=1;
						c[x][y]=tool+1;
						dfs(xx,yy,tool+1,1);
						b[xx][yy]=0;
					}
				}
				else if(tool+2<c[xx][yy])
					if(t&&!b[xx][yy]){
						b[xx][yy]=1;
						a[xx][yy]=a[x][y];
						c[x][y]=tool+2;
						dfs(xx,yy,tool+2,0);
						a[xx][yy]=0;
						b[xx][yy]=0;
					}
				}
		}
}
int main(){
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;i++){
		long long x,y,num;
		scanf("%lld%lld%lld",&x,&y,&num);
		a[x][y]=num+1;
	}
	if(m==1){
		printf("0\n");
		return 0;
	}
	memset(c,0x3f,sizeof(c));
//	for(int i=1;i<=m;i++)
//		for(int j=1;j<=m;j++)
//			c[i][j]=INT_MAX;
	/*for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}
	*/
	b[1][1]=1;
	dfs(1,1,1,1);
	/*
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++)
			printf("%d ",c[i][j]);
		printf("\n");
	}
	*/
	if(ans==INT_MAX) printf("-1\n");
	else printf("%lld\n",ans);
	return 0;
}