#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;

int a[1005][1005];
bool vis[1005][1005];
int dis[1005][1005];
int m,n;

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

void dfs(int x,int y,int cost,int color){
	if(cost > dis[m][m])return ;
	if(x == m && y == m){
		dis[x][y] = min(dis[x][y] ,cost);
		return ;
	}
	for(int i = 0;i < 4;i ++){
		int nx = dx[i] + x;
		int ny = dy[i] + y;
		if(vis[nx][ny] || nx < 1 || nx > m || ny < 1 || ny > m){
			continue;
		}
		if(a[nx][ny] || color){
			if(! a[nx][ny]){
				if(cost + 2 > dis[nx][ny]){
					continue;
				}
				dis[nx][ny] = cost +2;
				vis[nx][ny] = true;
				dfs(nx,ny,cost + 2,color);
				vis[nx][ny] = false;
			}else if(a[nx][ny] == color && cost < dis[nx][ny]){
				vis[nx][ny] = true;
				dis[nx][ny] = cost;
				dfs(nx,ny,cost,color);
				vis[nx][ny] = false;
			}else if(a[nx][ny] != color && cost + 1 < dis[nx][ny]){
				dis[nx][ny] = cost + 1;
				vis[nx][ny] = true;
				dfs(nx,ny,cost + 1,a[nx][ny]);
				vis[nx][ny] = false;
			}
		}
	}
}

int main(){
	for(int i = 0;i < 1005;i ++)
		for(int j = 0;j < 1005;j ++)
			dis[i][j] = INF;
	cin>>m>>n;
	for(int i = 1;i <= n;i ++){
		int x,y,color;
		cin>>x>>y>>color;
		color ++;
		a[x][y] = color;
	}
	vis[1][1] = true;
	dfs(1,1,0,a[1][1]);
	if(dis[m][m] == INF)cout<<-1;
	else cout<<dis[m][m];
    return 0;
}