#include<bits/stdc++.h>
using namespace std;
int m,num,ma[1010][1010],ans=10010,d[1010][1010];
int fx[4]={-1,0,0,1},fy[4]={0,-1,1,0},flag[1010][1010];
void dfs(int x,int y,int color,int magic,int coin)
{
	if(x<=0||y<=0||x>m||y>m||flag[x][y]||coin>=d[x][y]) return;
	cout<<x<<" "<<y<<" "<<coin<<endl;
	if(x==m&&y==m)
	{
		ans=min(ans,coin);
		
		return;
	}
	d[x][y]=coin;
	
	for(int i=0;i<4;i++)
	{
		if(magic==1&&ma[x+fx[i]][y+fy[i]]==0) continue;
		flag[x][y]=1;
		if(magic==1&&ma[x+fx[i]][y+fy[i]]==color) dfs(x+fx[i],y+fy[i],color,0,coin);
		else if(magic==1&&ma[x+fx[i]][y+fy[i]]!=color) dfs(x+fx[i],y+fy[i],color,0,coin+1);
		else
		{
			if(ma[x+fx[i]][y+fy[i]]==color) dfs(x+fx[i],y+fy[i],color,0,coin);
			if(ma[x+fx[i]][y+fy[i]]==0) dfs(x+fx[i],y+fy[i],color,1,coin+2);
			else if(ma[x+fx[i]][y+fy[i]]!=color) dfs(x+fx[i],y+fy[i],ma[x+fx[i]][y+fy[i]],0,coin+1);
		}
		flag[x][y]=0;
	}
}
int main()
{
	cin>>m>>num;
	memset(d,127,sizeof(d));
	for(int i=1;i<=num;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		ma[x][y]=z+1;
	} 
	dfs(1,1,ma[1][1],0,0);
	if(ans<10010) cout<<ans;
	else cout<<"-1"<<endl;
}