#include<bits/stdc++.h>
using namespace std;
const int M=105;
int f[M][M],a[M][M],n,m;//f[i][j],在i，j的位置花费金币最小值,a存颜色
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
bool st[M][M];
int main()
{
	int x1,y1;
	cin>>m>>n;
	memset(f,0x3f,sizeof(f));
	memset(a,-1,sizeof(a));
	for(int i=1;i<=n;i++)
	{
		int x,y,c;
		cin>>x>>y>>c;
		a[x][y]=c;
	}
	f[1][1]=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=0;k<4;k++)
			{
				int x=i+dx[k],y=j+dy[k];
				if(x>0&&y>0&&x<=m&&y<=m)
				{
					if(a[i][j]!=-1)//有颜色 
					{
						if(a[x][y]==a[i][j])
						{
							f[i][j]=min(f[i][j],f[x][y]);
						}
						else if(a[x][y]!=a[i][j])
						{
							f[i][j]=min(f[i][j],f[x][y]+1);
						}	
					}
					else//没颜色 
					{
						st[i][j]=true;
						if(!st[x][y] and f[x][y]+2<f[i][j])
						{
							f[i][j]=min(f[i][j],f[x][y]+2);
							x1=x,y1=y;
						}
					}
				}

			}
			if(a[i][j]==-1)
			{
				a[i][j]=a[x1][y1];
			}
		}
	} 
	if(f[m][m]==0x3f3f3f3f)cout<<"-1";
	else cout<<f[m][m];                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               
}