#include<cstdio>
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int m,n,a[101][101],ans=0x7f7f7f7f;
bool p[101][101];
void dfs(int x,int y,int k,int t)
{
	if(k>ans)	return ;
	if(x==m&&y==m)
	{
		ans=k;
		return ;
	}
	for(int i=0;i<4;i++)
	{
		if(p[x+dx[i]][y+dy[i]]==0&&x+dx[i]>0&&x+dx[i]<=m&&y+dy[i]>0&&y+dy[i]<=m)
		{
			if(a[x+dx[i]][y+dy[i]]==-1&&t==1)
			{
				p[x+dx[i]][y+dy[i]]=1;
				a[x+dx[i]][y+dy[i]]=a[x][y];
				dfs(x+dx[i],y+dy[i],k+2,0);
				a[x+dx[i]][y+dy[i]]=-1;
				p[x+dx[i]][y+dy[i]]=0;
			}
			if(a[x+dx[i]][y+dy[i]]!=-1)
			{
				if(a[x][y]==a[x+dx[i]][y+dy[i]])
				{
					p[x+dx[i]][y+dy[i]]=1;
					dfs(x+dx[i],y+dy[i],k,1);
					p[x+dx[i]][y+dy[i]]=0;
				}
				else
				{
					p[x+dx[i]][y+dy[i]]=1;
					dfs(x+dx[i],y+dy[i],k+1,1);
					p[x+dx[i]][y+dy[i]]=0;
				}
			}
		}
	}
	return ;
}
int main()
{
//	freopen("chess.in","r",stdin);
//	freopen("chess.out","w",stdout);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++)
		{
			a[i][j]=-1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		scanf("%d",&a[x][y]);
	}
	dfs(1,1,0,1);
	if(ans==0x7f7f7f7f)	printf("-1\n");
	else	printf("%d\n",ans);
	return 0;
}

TLE求调谢谢