#include<bits/stdc++.h>
using namespace  std;
int a[105][105];
int js=-1,m;
bool vis[105][105];
int p1[4]={1,-1,0,0},p2[4]={0,0,-1,1};
void dfs(int x1,int y1,int c,bool pd,int ans)
{
	if(ans>=js&&js!=-1)
	{
		return;
	}
	if(x1==m&&y1==m)
	{
		if(js==-1)
		{
			js=ans;
		}
		else
		{
			js=min(ans,js);
		}
		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)
				{
					vis[x1-p1[i]][y1-p2[i]]=1;
					dfs(x1-p1[i],y1-p2[i],c,1,ans);
					vis[x1-p1[i]][y1-p2[i]]=0;
				}
				else if(a[x1-p1[i]][y1-p2[i]]==1||a[x1-p1[i]][y1-p2[i]]==0)
				{
					
					vis[x1-p1[i]][y1-p2[i]]=1;
					dfs(x1-p1[i],y1-p2[i],a[x1-p1[i]][y1-p2[i]],1,ans+1);
					vis[x1-p1[i]][y1-p2[i]]=0;
				}
				else if(a[x1-p1[i]][y1-p2[i]]==2&&pd)
				{
					vis[x1-p1[i]][y1-p2[i]]=1;
					a[x1-p1[i]][y1-p2[i]]=c;
					dfs(x1-p1[i],y1-p2[i],c,0,ans+2);
					vis[x1-p1[i]][y1-p2[i]]=0;
					a[x1-p1[i]][y1-p2[i]]=2;
				}
				else
				{
					return;
				}
			}
		}
	}
	return;
}
int main()
{
	int n,x,y,c;
	cin>>m>>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++)
	{
		cin>>x>>y>>c;
		a[x][y]=c;
	}
	dfs(1,1,a[1][1],1,0);
	cout<<js;
	return 0;
}