#include<bits/stdc++.h>
using namespace std;
int n,m,color[1100][1100];
int flag[1100][1100];
int d[1100][1100];
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
int minn=0x7f;
bool check(int x,int y)
{
	if(x<1||x>n||y<1||y>n)
		return false;
	return true;
}
void dfs(int x,int y,int coin,int last_color)
{
	if(x==n&&y==n)
	{
		minn=min(coin,minn);
		return;
	}
	for(int i=0;i<4;i++)
	{
		int nx=dx[i]+x;
		int ny=dy[i]+y;
		if(check(nx,ny)==true)
		{
			if(flag[nx][ny]==0)
			{
				if(color[x][y]!=0||color[nx][ny]!=0)
				{
					if(color[nx][ny]==0)
					{
						if(coin+2<d[nx][ny])
						{
							flag[nx][ny]=1;
							d[nx][ny]=coin+2;
							dfs(nx,ny,coin+2,last_color);
							flag[nx][ny]=0;
						}
					}
					else
					{
						if((last_color==color[nx][ny])&&(coin<d[nx][ny]))
						{
							flag[nx][ny]=1;
							d[nx][ny]=coin;
							dfs(nx,ny,coin,last_color);
							flag[nx][ny]=0;
						}
						else if((coin+1<minn)&&(coin+1<d[nx][ny]))
						{
							flag[nx][ny]=1;
							d[nx][ny]=coin+1;
							dfs(nx,ny,coin+1,color[nx][ny]);
							flag[nx][ny]=0;
						}
					}
				} 
			}
		}
	}
}
int main()
{
	cin>>n>>m;
	memset(d,0x7f,sizeof(d));
	memset(flag,0,sizeof(flag));
	memset(color,0,sizeof(color));
	for(int i=1;i<=m;i++)
	{
		int cx,cy,cc;
		cin>>cx>>cy>>cc;
		color[cx][cy]=cc+1;
	}
	flag[1][1]=1;
	dfs(1,1,0,color[1][1]);
	if(minn==0x7f)
		cout<<-1;
	else
		cout<<minn;
	return 0;
}