#include <bits/stdc++.h>
using namespace std;

struct mmm
{
	int money = 0;
	char c = 'w'; //默认白色
	bool magic = false;
} mapa[1001][1001];
int m, n;
bool b[1001][1001];
int xx[5] = {0, 0, 1, 0, -1};
int yy[5] = {0, 1, 0, -1, 0};
void dfs(int x, int y, int mon)
{
	if (mon >= mapa[m][m].money)
	{
		return;
	}
	mapa[x][y].money = min(mapa[x][y].money, mon);
	int tx, ty, q;
	for (q = 1; q <= 4; ++q)
	{
		tx = x + xx[q];
		ty = y + yy[q];
		if (tx >= 1 && tx <= m && ty >= 1 && ty <= m &&
			b[tx][ty] == false)
		{
			b[tx][ty] = true;
			if (mapa[x][y].c == mapa[tx][ty].c &&
				mapa[x][y].c != 'w')
			{
				dfs(tx, ty, mon);
			}
			else if (mapa[tx][ty].c != mapa[x][y].c &&
					 mapa[tx][ty].c != 'w' && mapa[x][y].c != 'w')
			{
				dfs(tx, ty, mon + 1);
			}
			else if (mapa[tx][ty].c == 'w')
			{
				if (mapa[x][y].magic == true)
				{
					b[tx][ty] = false;
					continue;
				}
				else //上一步的magic==false就说明上一个不是white
				{
					mapa[tx][ty].c = mapa[x][y].c;
					mapa[tx][ty].magic = true;
					dfs(tx, ty, mon + 2);
					mapa[tx][ty].c = 'w';
					mapa[tx][ty].magic = false;
				}
			}
			b[tx][ty] = false;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> m >> n;
	int i, j, x, y, t;
	for (i = 1; i <= m; ++i)
	{
		for (j = 1; j <= m; ++j)
		{
			mapa[i][j].money = INT_MAX;
		}
	}
	for (i = 1; i <= n; ++i)
	{
		cin >> x >> y >> t;
		if (t == 1)
		{
			mapa[x][y].c = 'y'; // 1代表黄色
		}
		else
		{
			mapa[x][y].c = 'r'; // 2代表红色
		}
	}
	dfs(1, 1, 0);
	if (mapa[m][m].money != INT_MAX)
	{
		cout << mapa[m][m].money;
	}
	else
	{
		cout << "-1";
	}
	return 0;
}