#include<bits/stdc++.h>
using namespace std;
int m,n;
int a[105][105],us[105][105];
bool vis[105][105];
int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
int minn=INT_MAX;
bool flag;
void dfs(int x,int y,int use,bool f)//f表示能不能用魔法
{
	//cout<<x<<" "<<y<<" "<<use<<" "<<f<<endl;
	if(use>minn)return ;
	if(x==m&&y==m)
	{
		minn=min(minn,use);
		flag=1;
		return ;
	}
	//if(vis[x][y])return ;
	//vis[x][y]=1;
	for(int i=1;i<=4;i++)
	{
		int u=x+dx[i],v=y+dy[i];
		if(u>=1&&u<=m&&v>=1&&v<=m)
		{
			if(!vis[u][v])
			{
				if(!a[u][v])
				{
					if(!f)
					{
						if(use+2<us[u][v])
						{
							a[u][v]=a[x][y];
							f=1;
							vis[u][v]=1;
							us[u][v]=use+2;
							dfs(u,v,use+2,f);
							f=0;
							a[u][v]=0;
							vis[u][v]=0;
						}
						
					}
					//else return ;
				}
				else if(a[u][v])
				{
					if(f)f=0;
					
					if(a[x][y]!=a[u][v])
					{
						if(use+1<us[u][v])
						{
							vis[u][v]=1;
							us[u][v]=use+1;
							dfs(u,v,use+1,f);
							vis[u][v]=0;
						}
						
					}
					else 
					{
						if(use<us[u][v])
						{
							vis[u][v]=1;
							us[u][v]=use;
							dfs(u,v,use,f);
							vis[u][v]=0;
						}
						
					}
					
				}
			}
		}
	}
}
int main()
{
	cin>>m>>n;
	memset(us,0x7f,sizeof(us));
	for(int i=1;i<=n;i++)
	{
		int x,y,p;
		cin>>x>>y>>p;
		a[x][y]=p+1;
	}
	vis[1][1]=1;
	dfs(1,1,0,0);
	if(!flag)
	{
		cout<<-1;
		return 0;
	}
	cout<<minn;
	return 0;
}