#include<iostream> 
#include<queue>
#include<cmath>
//#include<algorithm>
using namespace std;

struct loc{
	int x,y,c;
};
int map[101][101]={0},dp[101][101];
int m;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
queue<loc> q;

void bfs(int x,int y)
{
	loc t,nxt;
	t.x=x;
	t.y=y;
	t.c=map[x][y];
	dp[x][y]=0;
	//t.m=1;
	q.push(t);
	while(!q.empty())
	{
		t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			nxt.x=t.x+dir[i][0];
			nxt.y=t.y+dir[i][1];
			if(!(nxt.x>0 && nxt.y>0 && nxt.x<=m && nxt.y<=m))
				continue;
			nxt.c=map[nxt.x][nxt.y];
			if(t.c<0 && nxt.c==0)
				continue;
			else if(t.c>0 && nxt.c==0)
			{
				if(dp[nxt.x][nxt.y]!=-1)
					//dp[nxt.x][nxt.y]=min(dp[nxt.x][nxt.y],dp[t.x][t.y]+2);
				{
					if(dp[nxt.x][nxt.y]>dp[t.x][t.y]+2)
					{
						dp[nxt.x][nxt.y]=dp[t.x][t.y]+2;
						nxt.c=-t.c;
						q.push(nxt);
					}
				}
				else
				{
					dp[nxt.x][nxt.y]=dp[t.x][t.y]+2;
					nxt.c=-t.c;
					q.push(nxt);
				}
			}
			else if(abs(t.c)==nxt.c)
			{
				if(dp[nxt.x][nxt.y]!=-1)
				{
					if(dp[nxt.x][nxt.y]>dp[t.x][t.y])
					{
						dp[nxt.x][nxt.y]=dp[t.x][t.y];
						map[nxt.x][nxt.y]=-3;
						q.push(nxt);
					}
				}
				else
				{
					dp[nxt.x][nxt.y]=dp[t.x][t.y];
					q.push(nxt);
				}
			}
			else if(abs(t.c)!=nxt.c)
			{
				if(dp[nxt.x][nxt.y]!=-1)
				{
					if(dp[nxt.x][nxt.y]>dp[t.x][t.y]+1)
					{
						dp[nxt.x][nxt.y]=dp[t.x][t.y]+1;
						q.push(nxt);
					}
				}
				else
				{
					dp[nxt.x][nxt.y]=dp[t.x][t.y]+1;
					q.push(nxt);
				}
			}
		}
	}
}

int main()
{	
	int x,y,c,n;
	cin>>m>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x>>y>>c;
		map[x][y]=c+1;
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++)
			dp[i][j]=-1;
	}
	bfs(1,1);
	cout<<dp[m][m];
	return 0;
}