#include <bits/stdc++.h>

using namespace std;

const int N = 110, M = 1000;

int g[N][N];

int n, m;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int dist[N][N];

int main(){

	

	memset(dist, 0x3f, sizeof dist);

	cin >> n >> m;

	for (int i = 1; i <= m; i ++){

		int x, y, o; cin >> x >> y >> o;

		g[x][y] = (o == 0 ? 1 : 2);

	}

	

	queue<array<int, 5>> q;

	

	q.push({1, 1, 1, g[1][1], 0});

	

	dist[1][1] = 0;

	

	while (!q.empty()){

		auto [sx, sy, status, p, distance] = q.front(); q.pop();

		// cout << sx << ' ' << sy << endl;

		// cout << sx << ' ' << sy << ' ' << status << endl;

		

		for (int i = 0; i < 4; i ++){

			int tx = sx + dx[i], ty = sy + dy[i];

			if (tx < 1 || tx > n || ty < 1 || ty > n) continue;

		

			// if (tx == 4 && ty == 4) cout << "what is it ???   " << sx << ' ' << sy << ' ' << status << ' ' << p << ' ' <<  dist[sx][sy] << endl;

			if (status && g[tx][ty] == 0 && dist[tx][ty] > distance + 2){

				dist[tx][ty] = dist[sx][sy] + 2;

				q.push({tx, ty, 0, p, dist[tx][ty]});

			}else if ((p & g[tx][ty]) && dist[tx][ty] > distance){

				dist[tx][ty] = dist[sx][sy];

				// if (status == 0) status = 1;

				int f = (status == 0 ? 1 : status);

				q.push({tx, ty, f, g[tx][ty], dist[tx][ty]});

			}else if (g[tx][ty] && !(p & g[tx][ty]) && dist[tx][ty] > distance + 1){

				dist[tx][ty] = dist[sx][sy] + 1;

				// if (status == 0) status = 1;

				int f = (status == 0 ? 1 : status);

				q.push({tx, ty, f, g[tx][ty], dist[tx][ty]});

			}

		}

	}

	

	// for (int i = 1; i <= n; i ++){

		// for (int j = 1; j <= n; j ++){

			// if (dist[i][j] == 0x3f3f3f3f) cout << -1 << ' ';

			// else cout << dist[i][j] << ' ';

		// }

		// cout << "\n";

// 		

	// }

// 	

	

	

	cout << (dist[n][n] == 0x3f3f3f3f ? -1 : dist[n][n]) << "\n";

		

}