#include<bits/stdc++.h>
using namespace std;
int m,n,x,y,c,_s[105][105],ans=0x3f3f3f3f,sq[105][105],dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
bool flag[105][105];
bool l(int x,int y){
    return (x>=1&&x<=m&&y>=1&&y<=m);
}
void dfs(int x,int y,bool f,int s){
    if(s>_s[x][y]){
        return;
    }
    _s[x][y]=s;
    int nx,ny;
    for(int i=1;i<=4;i++){
        nx=x+dx[i],ny=y+dy[i];
        if(l(nx,ny)&&!flag[nx][ny]){
            if(sq[nx][ny]==-1){
                if(f){
                    continue;
                }
                s+=2;
                if(s>_s[nx][ny]){
                    continue;
                }
                _s[nx][ny]=s;
                sq[nx][ny]=sq[x][y];
                flag[nx][ny]=true;
                if(nx==m&&ny==m){
                    ans=min(ans,s);
                }else{
                    dfs(nx,ny,1,s);
                }
                s-=2;
                sq[nx][ny]=-1;
                flag[nx][ny]=false;
            }else{
                if(sq[nx][ny]==sq[x][y]){
                    if(s>_s[nx][ny]){
                        continue;
                    }
                    _s[nx][ny]=s;
                    flag[nx][ny]=true;
                    if(nx==m&&ny==m){
                        ans=min(ans,s);
                    }else{
                        dfs(nx,ny,0,s);
                    }
                    flag[nx][ny]=false;
                }else{
                    s++;
                    if(s>_s[nx][ny]){
                        continue;
                    }
                    _s[nx][ny]=s;
                    flag[nx][ny]=true;
                    if(nx==m&&ny==m){
                        ans=min(ans,s);
                    }else{
                        dfs(nx,ny,0,s);
                    }
                    flag[nx][ny]=false;
                    s--;
                }
            }
        }
    }
}
int main(){
    memset(sq,-1,sizeof(sq));
    memset(_s,0x3f,sizeof(_s));
    cin>>m>>n;
    if(m==1){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++){
        cin>>x>>y>>c;
        sq[x][y]=c;
    }
    dfs(1,1,0,0);
    if(ans==0x3f3f3f3f){
        cout<<-1;
        return 0;
    }
    cout<<ans;
    return 0;
}