#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll m,n;
int dx[4]= {0,0,1,-1};
int dy[4]= {-1,1,0,0};
ll dp[100][100]= {0};//颜色是什么
bool a[100][100];//走没走过
int flag=0;//使没使用过魔法
int dfs(int x,int y) {
	ll ans=0;
	int fx,fy;
	if(x==m && y==m) {
		return ans;
	}
	for(int i=1; i<=4; i++) {
		fx=x+dx[i];
		fy=y+dy[i];
		if(flag==1 && (fx<1 || fy<0 || fx>m || fy>m || a[fx][fy]==true)) {
			return -1;
		} else flag=0;
		if(fx<1 || fy<0 || fx>m || fy>m || a[fx][fy]==true) {
			continue;
		}
		if(dp[fx][fy]==0) {
			dp[fx][fy]=dp[x][y];
			ans+=2;
			flag=1;
		}
		if(dp[fx][fy]!=dp[x][y]) {
			ans+=1;
		}
		if(!(fx<1 || fy<1 || fx>m || fy>m)) {
			a[fx][fy]==true;
		}
	}
	dfs(fx,fy);
}
int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	a[0][0]=false;
	cin>>m>>n;
	for(int i=0; i<n; i++) {
		int x,y,c;
		cin>>x>>y>>c;
		if(c==1) {
			dp[x][y]=1;
		}
		if(c==0) {
			dp[x][y]=2;
		}
	}
	ll num=dfs(0,0);
	cout<<num<<"\n";
	return 0;
}//2是red，1是yellow