#include<bits/stdc++.h>
using namespace  std;
int a[1001][1001];
long long js=-1;
int m;
bool vis[1001][1001];
int p1[4]={1,0,-1,0},p2[4]={0,1,0,-1};
void read(int &x)
{
	int f=1;
	x=0;
	char ch=getchar();
	if(ch<'0'||ch>'9')
	{
		f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x*=10;
		x+=ch-'0';
		ch=getchar();
	}
	x*=f;
}
void dfs(int x1,int y1,int c,bool pd,long long ans)
{
	vis[x1][y1]=1;
	c=a[x1][y1];
	//cout<<x1<<' '<<y1<<"\n";
	if(ans>=js&&js!=-1)
	{
		vis[x1][y1]=0;
		return;
	}
	if(x1==m&&y1==m)
	{
		js=ans;
		vis[x1][y1]=0;
		return;
	}
	for(int i=0;i<=3;i++)
	{
		if(x1-p1[i]>=1&&x1-p1[i]<=m&&y1-p2[i]>=1&&y1-p2[i]<=m)
		{
			if(!vis[x1-p1[i]][y1-p2[i]])
			{
				if(a[x1-p1[i]][y1-p2[i]]==c)
				{
					dfs(x1-p1[i],y1-p2[i],c,1,ans);
				}
				else if(a[x1-p1[i]][y1-p2[i]]!=2)
				{
					dfs(x1-p1[i],y1-p2[i],a[x1-p1[i]][y1-p2[i]],1,ans+1);
				}
				else if(a[x1-p1[i]][y1-p2[i]]==2&&pd)
				{
					a[x1-p1[i]][y1-p2[i]]=c;
					dfs(x1-p1[i],y1-p2[i],c,0,ans+2);
					a[x1-p1[i]][y1-p2[i]]=2;
				}
			}
		}
	}
	vis[x1][y1]=0;
	return;
}
int main()
{
	int n,x,y,c;
	read(m);
	read(n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[i][j]=2;
		}
	}
	for(int i=1;i<=n;i++)
	{
		read(x);
		read(y);
		read(c);
		a[x][y]=c;
	}
	dfs(1,1,a[1][1],1,0);
	printf("%lld",js);
	return 0;
}