#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int map[1001][1001], book[1001][1001], n, m, sx, sy, fx, fy;
int nx[4] = {1, -1, 0, 0}, ny[4] = {0, 0, -1, 1}, min_cost = 1000000000;
void DFS(int x, int y, int magic, int cost)
{
	if (cost > min_cost) return ;
	if (x > n || y > n || x < 1 || y < 1) return ;
	if (x == fx && y == fy)
	{
		if (cost < min_cost) min_cost = cost;
		return ;
	}
	for (int i = 0; i < 4; i++)
	{
		int xx = x + nx[i], yy = y + ny[i];
		if (xx > n || yy > n || xx < 1 || yy < 1 || map[xx][yy] == 0 || book[xx][yy] == 1)
			continue;
		else if (map[xx][yy] > 0 && book[xx][yy] == 0)
		{
			book[xx][yy] = 1;
			if (map[xx][yy] != map[x][y]) DFS(xx, yy, magic, cost + 1);
			else DFS(xx, yy, magic, cost);
			book[xx][yy] = 0;
		}
		else if (magic == 0 && book[xx][yy] == 0)
		{
			map[xx][yy] = map[x][y];
			book[xx][yy] = 1;
			DFS(xx, yy, 1, cost + 2);
			map[xx][yy] = 0;
			book[xx][yy] = 0;
		}
		if (magic == 1) 
		{
			map[x][y] = 0;
			magic = 0;
		}
	}
	return ;
}
int main()
{
    cin >> n >> m;
    sx = 1; sy = 1; fx = n; fy = n;
    for (int i = 0; i < m; i++)
    {
    	int x, y, z;
    	cin >> x >> y >> z;
    	map[x][y] = z + 1;
	}
	DFS(sx, sy, 0, 0);
	cout << ((min_cost == 1000000000) ? -1 : min_cost);
	return 0;
}