#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node {
	int x, y, cost, flag; //flag=0说明没用魔法  flag=1说明当前歌为1号颜色 flag=2表示颜色为2号
};
bool operator<(node a, node b) {
	return a.cost > b.cost;
}
priority_queue<node>q;
int color[101][101], book[101][101];
int m, n;
int dx[5] = {0, 0, 1, 0, -1};
int dy[5] = {0, 1, 0, -1, 0};
void bfs() {
	memset(book, 0x3f3f3f3f, sizeof(book));
	book[1][1] = 0;
	q.push({1, 1, 0, 0});
	while (!q.empty()) {
		node now = q.top();
		//cout<<now.x<<' '<<now.y<<' '<<now.cost<<' '<<now.flag<<endl;
		q.pop();
		for (long long i = 1; i <= 4; i++) {
			int xx = now.x + dx[i];
			int yy = now.y + dy[i];
			if (xx >= 1 && xx <= m && yy >= 1 && yy <= m) {
				//当前格子没用魔法 两个格子颜色相同
				int cost = now.cost;
				if (color[now.x][now.y] == color[xx][yy] && now.flag == 0 && book[xx][yy] > cost && color[xx][yy] != 0) {

					q.push({xx, yy, cost, 0});
					book[xx][yy] = cost;
				}
				//当前格子没用魔法 两个格子颜色不同
				else if (color[now.x][now.y] != color[xx][yy] && color[xx][yy]!=0 && color[now.x][now.y] != 0 && now.flag == 0 && book[xx][yy] > cost + 1) {
					book[xx][yy] = cost + 1;
					q.push({xx, yy, cost + 1, 0});
				}
				//3.当前格子没用魔法 并且xx yy格无色
				else if (now.flag == 0 && color[xx][yy] == 0 && color[now.x][now.y] != 0 && book[xx][yy] > cost + 2) {
					book[xx][yy] = cost + 2;
					q.push({xx, yy, cost + 2, color[now.x][now.y]});
				}
				//4.上一步用了魔法  颜色相同
				else if(now.flag==color[xx][yy]&&now.flag!=0&&color[xx][yy]!=0&&cost<book[xx][yy]){
					book[xx][yy]=cost;
					q.push({xx,yy,cost,0});
				}
				//5.上一步用了魔法 颜色不同
				else if(now.flag!=color[xx][yy]&&now.flag!=0&&color[xx][yy]!=0&&cost<book[xx][yy]&&book[xx][yy]>cost+1){
					book[xx][yy]=cost+1;
					q.push({xx,yy,cost+1,0});
				}
			}
		}
	}
	if(book[m][m]==0x3f3f3f3f){
		cout<<-1<<endl;
	}
	else cout<<book[m][m]<<endl;
	return;
}
signed main() {
	cin >> m >> n;
	while (n--) {
		int x, y, c;
		cin >> x >> y >> c;
		color[x][y] = ++c;
	}
	bfs();
	return 0;
}