#include <iostream>
#include <cstring>
#include <queue>
#include <string>
#include <utility>
#include <algorithm>
#include <iomanip>
using namespace std;
using PII = pair<int, int>;
const int N = 110;
int g[N][N];
int dist[N][N];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
int n, m;
struct point
{
	int x, y;
	int color;
	bool f;
};

int bfs()
{
	memset(dist,0x3f,sizeof dist);
	queue<point> q;

	dist[1][1] = 0;
	q.push({1,1,g[1][1]});
	
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		int x = t.x, y = t.y;

		int color = t.color;
		bool f = t.f;

		for (int i = 0; i < 4; ++i)
		{
			int tx = x + dx[i], ty = y + dy[i];
			if (tx >= 1 && ty >= 1 && tx <= m && ty <= m )
			{
				if (g[tx][ty] == -1) // gray
				{
					if (f)
						continue;
					if (dist[tx][ty] > dist[x][y] + 2)
					{
						dist[tx][ty] = dist[x][y] + 2;
						q.push({ tx,ty,g[x][y],1 });
					}
				}
				else if (g[tx][ty] != color) // not same
				{
					if (dist[tx][ty] > dist[x][y] + 1)
					{
						dist[tx][ty] = dist[x][y] + 1;
						q.push({ tx,ty,g[tx][ty] });
					}
				}
				else
				{
					if (dist[tx][ty] > dist[x][y])
					{
						dist[tx][ty] = dist[x][y];
						q.push({ tx,ty,g[tx][ty] });
					}
				}
			}
		}
	}

	return dist[m][m] == 0x3f3f3f3f ? -1 : dist[m][m];
}

void solve()
{
	
	cin >> m >> n;
	memset(g, -1, sizeof g);
	while (n--)
	{
		int a, b, c; cin >> a >> b >> c;
		g[a][b] = c;
	}
	
	
	cout << bfs() << endl;
	
/*	
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=m;++j)
		cout<<setw(3)<<g[i][j]<<" ";
		cout<<endl;
	}
	
	cout<<endl;
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(dist[i][j]==0x3f3f3f3f)
			cout<<setw(3)<<-1<<" ";
			else
			cout<<setw(3)<<dist[i][j]<<" ";
			
		}
		cout<<endl;
	}
*/ 
}

int main()
{
	solve();
	return 0;
}