#include<cstdio>
#include<string.h> 
#include<iostream>
using namespace std;
const int N=1e4;
int a[105][105],coinless=N*2,dx[]={0,1,-1,0,0},dy[]={0,0,0,-1,1},m,n;
bool vis[105][105];
void dfs(int x,int y,int coin,bool magic,int color)
{
	int gx,gy;
	if(coin>=coinless) return;
	if(x==m&&y==m)
	{
		coinless=min(coinless,coin);
		return;
	}
	for(int i=1;i<=4;i++)
	{
		gx=x+dx[i],gy=y+dy[i];
		if(gx<=0||gx>m||gy<=0||gy>m||(a[gx][gy]==-1&&magic)||vis[gx][gy]) continue;
		if(a[gx][gy]==-1)
		{
			vis[gx][gy]=true;
			dfs(gx,gy,coin+2,true,a[x][y]);
		}
		else if(a[gx][gy]=!a[x][y])
		{
			vis[gx][gy]=true;
			dfs(gx,gy,coin+1,false,a[gx][gy]);
		}
		else
		{
			vis[gx][gy]=true;
			dfs(gx,gy,coin,false,a[gx][gy]);
		}
	}
	return;
}
int main()
{
	memset(vis,false,sizeof(vis));
	memset(a,-1,sizeof(a));
	int i,tmp1,tmp2,tmp3;
	scanf("%d%d",&m,&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&tmp1,&tmp2,&tmp3);
		a[tmp1][tmp2]=tmp3;
	}
	vis[1][1]=true;
	dfs(1,1,0,false,a[1][1]);
	if(coinless==N*2) printf("-1\n");
	else printf("%d\n",coinless);
}