#include<iostream>
using namespace std;
int m,n,a[105][105],mins=100000000,s,b[105][105];
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
void dfs(int x,int y,int z)
{
	if(mins<=s)return ;
	if(x==m&&y==m)
	{
		mins=min(mins,s);
		return ;
	}
	for(int i=1;i<=4;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1||nx>m||ny<1||ny>m||b[nx][ny]==1||(z!=-1&&a[nx][ny]==0))continue;
		int q=0,nz=-1;
		b[nx][ny]=1;
		if(a[x][y]==1)
		{
			if(a[nx][ny]==2)q=1;
			if(a[nx][ny]==0)
			{
				q=2;
				nz=1;
			}
		}
		if(a[x][y]==2)
		{
			if(a[nx][ny]==1)q=1;
			if(a[nx][ny]==0)
			{
				q=2;
				nz=2;
			}
		}
		if(z!=-1)
		{
			if(z!=a[nx][ny])q=1;
		}
		s+=q;
		dfs(nx,ny,nz);
		s-=q;
		b[nx][ny]=0;
	}
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y,u;
		cin>>x>>y>>u;
		a[x][y]=u;
		if(u==0)a[x][y]=2;
	}
	b[1][1]=1;
	dfs(1,1,-1);
	if(mins==100000000)cout<<-1;
	else cout<<mins;
	return 0;
}