#include <bits/stdc++.h>
using namespace std;
int m,n,qmap[1010][1010];
int dx[5]= {0,0,0,1,-1},dy[5]= {0,1,-1,0,0},minx=0x7f,cost[1010][1010];
bool vis[1010][1010];
void dfs(int x,int y,int c,int now) {
	if(x==m&&y==m) {
		minx=min(c,minx);
		return;
	}
	for(int i=1; i<=4; i++) {
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<=m&&nx>=1&&ny<=m&&ny>=1&&!vis[nx][ny]&&(qmap[x][y]||qmap[nx][ny])) {
			if(qmap[nx][ny]==0&&c+2<cost[nx][ny]) {
				vis[nx][ny]=1;
				cost[nx][ny]=c+2;
				dfs(nx,ny,c+2,now);
				vis[nx][ny]=0;
			}
			else if((now==qmap[nx][ny])&&(c<cost[nx][ny])) {
				vis[nx][ny]=1;
				cost[nx][ny]=c;
				dfs(nx,ny,c,now);
				vis[nx][ny]=0;
			}
			else if((c+1<minx)&&(c+1<cost[nx][ny])) {
				vis[nx][ny]=1;
				cost[nx][ny]=c+1;
				dfs(nx,ny,c+1,qmap[nx][ny]);
				vis[nx][ny]=0;
			}
		}
	}
	return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	memset(cost,0x7f,sizeof(cost));
	for(int i=1; i<=n; i++) {
		int x,y,c;
		cin>>x>>y>>c;
		qmap[x][y]=c+1;
	}
	vis[1][1]=1;
	dfs(1,1,0,qmap[1][1]);
	if(minx==0x7f) cout<<"-1";
	else cout<<minx;
	return 0;
}