#13 #19 #20错误，大概是什么还没考虑，但已经想不出了

#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>
#define N 110

using namespace std;

int xx[] = { 1,-1,0,0 };
int yy[] = { 0,0,1,-1 };
int dist[N][N];
int vis[N][N];
int map[N][N];
int m, n, a, b, c, d;

int IsSafe(int x, int y)
{
	return (x < 0 || y < 0 || x >= m || y >= m) ? 0 : 1;

}

struct point
{
	int mx;
	int my;
	int vis;
	int dist;
	int IsMagic;
	int order;
}str, str2;

bool compareDist(const point& a, const point& b) {
	return a.order < b.order;
}

int BFS()
{
	memset(dist, -1, sizeof dist);
	dist[0][0] = 0;
	vis[0][0] = map[0][0];
	int i;
	deque<point> s;
	s.push_front({ 0, 0, vis[0][0], 0,0 });
	while (!s.empty())
	{
		str = s.front();
		s.pop_front();

		if (str.mx == m - 1 && str.my == m - 1)
		{
			return str.dist;
		}

		for (i = 0;i < 4;i++)
		{
			int o = str.mx + xx[i];
			int p = str.my + yy[i];
			if (!IsSafe(o, p))continue;
			if (dist[o][p] != -1)continue;

			if ((map[o][p] == str.vis) && map[o][p] != -1)//0入队头
			{
				dist[o][p] = str.dist;
				s.push_front({ o, p, map[o][p], str.dist ,min(0,str.IsMagic),0 });
				continue;
			}

			if (map[o][p] != str.vis && map[o][p] != -1 && str.vis != -1)//路长为1的部分做了个插入，插入0和2的中间
			{
				auto it = lower_bound(s.begin(), s.end(), point{ 0, 0, 0, 0, 0, 1 }, compareDist);
				s.insert(it, { o,p,map[o][p],str.dist + 1,min(0,str.IsMagic),1 });
				dist[o][p] = str.dist + 1;
				continue;
			}

			if (map[o][p] == -1 && str.vis != -1 && str.IsMagic == 0)//魔法变色或许是这一块有问题，这里默认变成原来一样的颜色，路长为2，放在最后面，等大佬调教
			{
				s.push_back({ o, p , str.vis ,str.dist + 2 ,1,2 });
				dist[o][p] = str.dist + 2;
				continue;
			}

		}


	}

	return -1;
}

int main()
{
	cin >> m >> n;
	memset(map, -1, sizeof map);
	while (n--)
	{
		scanf("%d %d %d", &a, &b, &c);
		a--;b--;
		map[a][b] = c;
	}

	int ans = BFS();

	printf("%d\n", ans);


	return 0;
}