#include<bits/stdc++.h>
using namespace std;
int m,n,sum=1000,ans,a[110][110],c[110][110];
bool b[110][110];
int tx[]={0,1,0,-1},ty[]={1,0,-1,0};
void dfs(int x,int y){
	if(x==m && y==m) sum=min(ans,sum);
	b[x][y]=1;
	int nx,ny;
	for(int i=0;i<4;i++){
		nx=x+tx[i],ny=y+ty[i];
		if(!b[nx][ny]){
			if(a[x][y]>=-1 && a[nx][ny]>-1 && nx>=1 && nx<=m && ny>=1 && ny<=m){
				if(c[x][y]!=c[nx][ny]){
					ans++;
					dfs(nx,ny);
					ans--;
				}
				else if(c[x][y]==c[nx][ny]) dfs(nx,ny);
			}
			else if(a[x][y]>-1 && a[nx][ny]==-1 && nx>=1 && nx<=m && ny>=1 && ny<=m){
				ans+=2;
				c[nx][ny]=c[x][y];
				dfs(nx,ny);
				ans-=2;
				c[nx][ny]=a[nx][ny];
			}
		}
	}
	b[x][y]=0;
}
int main(){
	cin>>m>>n;
	int x,y,v;
	memset(a,-1,sizeof(a));
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&v);
		a[x][y]=v;
	}
	memcpy(c,a,sizeof(a));
	dfs(1,1);
	if(sum==1000) cout<<-1;
	else cout<<sum;
	return 0;
}