#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=110;
int f[N][N];
int c[N][N];
int n,m;
struct yee
{
	int x,y,s;
};
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
void bfs()
{
	queue<yee> q;
	q.push({1,1,0});
	f[1][1]=0;
	while(!q.empty())
	{
		yee t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int x=t.x+dx[i],y=t.y+dy[i];
			if(x<1||x>n||y<1||y>n)
				continue;
			if(!c[t.x][t.y])//当前是无色 
			{
				if(c[x][y]&&f[x][y]>t.s)//目标只能是有色 
				{
					f[x][y]=t.s;
					q.push({x,y,t.s});
				}
			}
			else//当前是有色 
			{
				if(c[x][y]==c[t.x][t.y]&&f[x][y]>t.s)
				{
					f[x][y]=t.s;
					q.push({x,y,t.s});
					
				}
				else if(c[x][y]==0&&f[x][y]>t.s+2)
				{
					f[x][y]=t.s+2;
					q.push({x,y,t.s+2});
				}
				else if(c[x][y]!=c[t.x][t.y]&&c[x][y]&&f[x][y]>t.s+1)
				{
					f[x][y]=t.s+1;
					q.push({x,y,t.s+1});
//					cout<<x<<" "<<y<<endl;
				}
			}
		}
	}
}
int main()
{
	memset(f,0x3f,sizeof f);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,d;
		scanf("%d %d %d",&a,&b,&d);
		c[a][b]=d+1;
	}
	bfs();
	if(f[n][n]==0x3f3f3f3f)
		printf("-1");
	else
		printf("%d",f[n][n]);
	return 0;
}