#include<bits/stdc++.h>
using namespace std;
int a[1005][1005];
bool vis[1005][1005];
int n,m,ans=1e9;
void dfs(int x,int y,int val){
	if(val>ans||x>n||y>n)return;
	if(x==n&&y==n){
		ans=min(ans,val);
		return;
	}
	if(a[x][y]==0){
		if(x-1>0&&a[x-1][y]&&!vis[x-1][y]){
			vis[x-1][y]=1;
			dfs(x-1,y,val+2);
			vis[x-1][y]=0;
		}
		if(y-1>0&&a[x][y-1]&&!vis[x][y-1]){
			vis[x][y-1]=1;
			dfs(x,y-1,val+2);
			vis[x][y-1]=1;
		}
		if(x+1<=n&&a[x+1][y]&&!vis[x+1][y]){
			vis[x+1][y]=1;
			dfs(x+1,y,val+2);
			vis[x+1][y]=1;
		}
		if(y+1<=n&&a[x][y+1]&&!vis[x][y+1]){
			vis[x][y+1]=1;
			dfs(x,y+1,val+2);
			vis[x][y+1]=1;
		}
		return;
	}
	if(x-1>0&&!vis[x-1][y]){
		vis[x-1][y]=1;
		dfs(x-1,y,val+2);
		vis[x-1][y]=0;
	}
	if(y-1>0&&!vis[x][y-1]){
		vis[x][y-1]=1;
		dfs(x,y-1,val+2);
		vis[x][y-1]=1;
	}
	if(x+1<=n&&!vis[x+1][y]){
		vis[x+1][y]=1;
		dfs(x+1,y,val+2);
		vis[x+1][y]=1;
	}
	if(y+1<=n&&!vis[x][y+1]){
		vis[x][y+1]=1;
		dfs(x,y+1,val+2);
		vis[x][y+1]=1;
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=z+1;
	}
	int d=dfs(1,1,a[1][1],0);
	if(d>=1e9)cout<<-1;
	else cout<<d;
	return 0;
}