#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,a[1005][1005],minn = 0x3f3f3f,num[1005][1005];
int dx[] = {-1,1,0,-1,0},dy[] = {-1,0,1,0,-1};
int dfs(int x,int y,int money)
{
	//cout<<x<<" "<<y<<" "<<money<<" "<<a[x][y]<<endl;
	if(x == n&&y == n) minn = min(minn,money);
	for(int i = 1;i <= 4;i++)
	{
		int xx = x + dx[i],yy = y + dy[i],money1 = money;
		if(xx > n||yy > n) continue; 
		if(a[xx][yy] != a[x][y]&&a[xx][yy] != -1) money1 ++;
		else if(a[xx][yy] == -1){
			if(xx == n&&yy == n) money1 += 2;
			else if(a[xx + 1][yy] != -1) 
			{
				if(a[xx + 1][yy] == a[x][y]) xx += 1,money1 += 2;
				else xx += 1,money1 += 3;
			}
			else if(a[xx][yy + 1] != -1){
				if(a[xx][yy + 1] == a[x][y]) yy += 1,money1 += 2;
				else yy += 1,money1 += 3;
			} 
		}
		if(money1 < num[xx][yy]&&(a[xx][yy] != -1||xx == n&&yy == n))
		{
			num[xx][yy] = min(num[xx][yy],money1);
			dfs(xx,yy,money1);
		}
	}
}
int main()
{ 
    scanf("%d%d",&n,&m);
    memset(a,-1,sizeof a);
    memset(num,0x3f3f3f,sizeof num);
    for(int i = 1;i <= m;i++)
    {
    	int x,y,z;
    	scanf("%d%d%d",&x,&y,&z);
    	a[x][y] = z;
	}
	dfs(1,1,0);
	if(minn == 0x3f3f3f) cout<<-1<<endl;
	else cout<<minn<<endl;
	return 0;
}