#include <bits/stdc++.h>
#define end cout<<"\n--------------------\n";system("pause")
using namespace std;
const int N=10005;
int n,m,ans=INT_MAX;
int a[N][N],Min[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
bool found=false,vi[N][N];
bool check(int x,int y){
    if(x<1||y<1||x>m||y>m)return false;
    if(vi[x][y])return false;
    return true;
}
void dfs(int x,int y,int cnt,int col){
    if(x==m&&y==m){
        found=true;
        ans=min(ans,cnt);
        return ;
    }
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(check(nx,ny)&&(a[x][y]||a[nx][ny])){
            if(a[nx][ny]==0){
                if(cnt+2<Min[nx][ny]){
                    vi[nx][ny]=true;
                    Min[nx][ny]=cnt+2;
                    dfs(nx,ny,cnt+2,col);
                    vi[nx][ny]=false;
                }
            }
            else{
                if(col==a[nx][ny]&&cnt<Min[nx][ny]){
                    vi[nx][ny]=true;
                    Min[nx][ny]=cnt;
                    dfs(nx,ny,cnt,col);
                    vi[nx][ny]=false;
                }
                else if(cnt+1<ans&&cnt+1<Min[nx][ny]){
                    vi[nx][ny]=true;
                    Min[nx][ny]=cnt+1;
                    dfs(nx,ny,cnt+1,col);
                    vi[nx][ny]=false;
                }
            }
        }
    }
}
int main(){
    cin >>m >>n;
    memset(a,0,sizeof(a));
    memset(vi,0,sizeof(vi));
    for(int i=1;i<=n;i++){
        int x,y,c;
        cin >>x >>y >>c;
        a[x][y]=c+1;
    }
    vi[1][1]=true;
    dfs(1,1,0,a[1][1]);
    cout <<(found?ans:-1);
    return 0;
}