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

const int MAXN = 1e2 + 7;
int n, m;
int a[MAXN][MAXN];
int vis[MAXN][MAXN];
int dix[10] = {0, 0, 1, -1};
int diy[10] = {1, -1, 0, 0};
int ans = 1e9;

void dfs(int x, int y, int cnt, bool flag)
{
	if (x == m && y == m)
	{
		ans = min(ans, cnt);
		return ;
	}
	if (vis[x][y] == 1)
		return ;
	vis[x][y] = 1;
	if (cnt > ans)
		return ;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dix[i];
		int ny = y + diy[i];
		if (nx >= 1 && nx <= m && ny >= 1 && ny <= m)
		{
			if (a[nx][ny] != -1)
			{
				if (a[nx][ny] == a[x][y])
					dfs(nx, ny, cnt, false);
				else
					dfs(nx, ny, cnt+1, false);
			}
			else
			{
				if (flag == false)
				{
					a[nx][ny] = a[x][y];
					dfs(nx, ny, cnt+2, true);
					a[nx][ny] = -1;
				}
				else
					continue;
			}
		}
	}
}


int main()
{
	cin >> m >> n;
	memset(a, -1, sizeof(a));
	memset(vis, 1e9, sizeof(vis));
	while (n--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		a[u][v] = w;
	}
	dfs(1, 1, 0, false);
	if (ans == 1e9)
	{
		cout << -1;
		return 0;
	}
	cout << ans << endl;
	return 0;
}