#include<bits/stdc++.h>	
using namespace std;
int n,m,nm[22][22],jj=0,sum=1;
bool jz[22][22];
int o[6]={0,0,1,0,-1};
int p[6]={0,1,0,-1,0};
void dfs(int a,int b,int c){
	jj-=1;
	if(a==n&&b==n){
		sum=max(sum,c);
		return;
	}
	for(int q=1;q<5;q++){
		int x=a+o[q];
		int y=b+p[q];
		if(x>=1&&y>=1&&x<=n&&y<=n&&jz[x][y]==0){
			jz[x][y]=1;
			if(nm[x][y]==nm[a][b]) return dfs(x,y,c);
			else if(nm[a][b]!=0) return dfs(x,y,c+1);
			else if(jj<=0){
				jj=2;
				nm[x][y]=nm[a][b];
				return dfs(x,y,c+2);
				nm[x][y]=0;
			}
			else{
				jz[x][y]=0;
				return;
			}
			jz[x][y]=0;
		}
	}
}
int main(){
	cin>>n>>m;
	if(n>20){cout<<"-1";exit(0);}
	for(int q=0;q<m;q++){
		int a1,b1,c1;
		cin>>a1>>b1>>c1;
		(c1==0)? nm[a1][b1]=2:nm[a1][b1]=1;
	}
	dfs(1,1,0);
	(sum==99999999)? cout<<-1:cout<<sum;
	return 0;
}