#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[100000][100000],g[100000][100000];
bool vis[100000][100000];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y,int con,int s,bool f){
	if(g[x][y]<=con) return;
	g[x][y]=con;
	for(int i=0;i<=3;i++){
		int tx=tx+dx[i];
		int ty=ty+dy[i];
		if(a[tx][ty]==0&&f==false){
			dfs(tx,ty,con+2,s,true);
		}else{
			if(a[tx][ty]==s){
				dfs(tx,ty,con,a[x][y],false);
			}
			if(a[tx][ty]!=s){
				dfs(tx,ty,con+1,a[x][y],false);
			}
		}
	}
}
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int b,c,d;
        cin>>b>>c>>d;
        a[b][c]=d+1;
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            g[i][j]=0xfffffff;
        }
    }
    dfs(1,1,0,-1,false);
    if(g[m][m]==0xfffffff){
        cout<<-1;
    }else{
        cout<<g[m][m];
    }
    return 0;
}