#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1e2 + 3;
int M,N;
int Box[Maxn][Maxn];
int C[Maxn][Maxn];
bool Flag[Maxn][Maxn],AnsT;
int X_[4] = {1,-1,0,0};
int Y_[4] = {0,0,1,-1};
void DFS(int X,int Y,int Cnt)
{
	//cout << X << " " << Y << endl;
	if(X == M && Y == M)
	{
		AnsT = true;
	}
	Flag[X][Y] = true;
	if(C[X][Y] <= Cnt && Flag[X][Y])
	{
		return ;
	}
	C[X][Y] = min(C[X][Y],Cnt);
	for(int i = 0;i < 4;i++)
	{
		if(!Flag[X_[i] + X][Y_[i] + Y])
		{
			if(X_[i] + X >= 1 && X_[i] + X <= M && Y_[i] + Y >= 1 && Y_[i] + Y <= M)
			{
				int Cost = 0;
				if((Box[X_[i] + X][Y_[i] + Y] == 1 && Box[X][Y] != 1) || (Box[X_[i] + X][Y_[i] + Y] == 0 && Box[X][Y] != 0))
				{
					Cost = 1;
					if(Box[X][Y] == -1)
					{
						Cost = 0;
					}
				}else if(Box[X_[i] + X][Y_[i] + Y] == -1)
				{
					Cost = 2;
					if(Box[X][Y] == -1)
					{
						//cout << "____ : "<< X << " " << Y << " " << X + X_[i] << " " << Y + Y_[i]<< endl;
						continue;
					}
				}
				DFS(X + X_[i],Y + Y_[i],Cnt + Cost);
			}
		}
	}
	Flag[X][Y] = false;
}
int main()
{
	memset(C,0x3f3f3f,sizeof(C));
	memset(Box,-1,sizeof(Box));
	cin >> M >> N;
	for(int i = 1;i <= N;i++)
	{
		int X,Y,C;
		cin >> X >> Y >> C;
		Box[Y][X] = C;
	}
	DFS(1,1,0);
	if(!AnsT)
	{
		cout << -1;
		return 0;
	}
	cout << C[M][M];
}