#include<bits/stdc++.h>
using namespace std;
int m,n;
struct node{
    int x;
    int y;
    int cl;
}a[1005];
bool b[1005][1005];
int ans=1e9;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
void dfs(int x,int y,int cmp,int col,bool lus){
    if(x==m && y==m){
        ans=min(ans,cmp);
        return;
    }
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<1 || xx>m || yy<1 || yy>m) continue;
        if(b[xx][yy]) continue;
        b[xx][yy]=true;
        bool flag=false;
        int fl;
        for(int j=1;j<=n;j++){
            if(a[j].x==xx && a[j].y==yy){
                flag=true;
                fl=a[j].cl;
                break;
            }
        }if(flag){
            if(fl==col)dfs(xx,yy,cmp+0,col,false);
            else dfs(xx,yy,cmp+1,fl,false);
        }else{
            if(!lus){
                dfs(xx,yy,cmp+2,col,true);
            }else{
                return;
            }
        }
    }
}
int main(){
    cin>>m>>n;
    int color;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y>>a[i].cl;
        if(a[i].x==1 && a[i].y==1) color=a[i].cl;
    }b[1][1]=true;
    dfs(1,1,0,color,false);
    if(ans==1e9) cout<<-1;
    else cout<<ans;
}