#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
	bool isUse;
	int color; 
};
int m,n,INF;
short color[110][110],
	dx[] = {0,1,-1,0,0},
	dy[] = {0,0,0,1,-1},
	vis[110][110];
queue<node> q;
void bfs(){
//	node tmp;tmp.color = 0;tmp.isUse = false;tmp.x = 1;tmp.y = 1;
	node tmp = {1,1,false,0};
	q.push(tmp);
	while(q.empty() == false){
		node u = q.front();
//		cout << u.x << " " << u.y << " " << vis[u.x][u.y] << endl;
		if(u.x == m and u.y == m){
//			cout << vis[m][m] << endl; 
			q.pop();
			continue;
		}
		for(int i = 1;i <= 4;i ++){
			int tx = u.x + dx[i],ty = u.y + dy[i];
			if(tx > 0 and tx <= m and ty > 0 and ty <= m){
				if(color[tx][ty] == 0){
					if(u.isUse == false){
						if(vis[u.x][u.y] + 2 < vis[tx][ty]){
							vis[tx][ty] = vis[u.x][u.y] + 2;
							node tmp = {tx,ty,true,color[u.x][u.y]};
							q.push(tmp);
						}
					}
					continue;
				}else if(color[u.x][u.y] == color[tx][ty] or u.color == color[tx][ty]){
					if(vis[u.x][u.y] < vis[tx][ty]){
						vis[tx][ty] = vis[u.x][u.y];
						node tmp = {tx,ty,false,0};
						q.push(tmp);
					}
				}else{
					if(vis[u.x][u.y] + 1 < vis[tx][ty]){
						vis[tx][ty] = vis[u.x][u.y] + 1;
						node tmp = {tx,ty,false,0};
						q.push(tmp);
					}
				}
			}
		}
		q.pop();
	}
}
int main(){
	cin >> m >> n;
	for(int i = 1,x,y,c;i <= n;i ++){
		cin >> x >> y >> c;
		color[x][y] = c + 1;
	}
//	for(int i = 1;i <= m;i ++){
//		for(int j = 1;j <= m;j ++){
//			cout << color[i][j] << " ";
//		} 
//		cout << endl;
//	}
	memset(vis,127,sizeof(vis));
	INF = vis[0][0];
	vis[1][1] = 0; 
	bfs();
	if(vis[m][m] == INF){
		cout << -1;
	}else{
		cout << vis[m][m];
	}
	return 0;
}