#include<bits/stdc++.h>
using namespace std;
int n,m;
// int a[1010][3];
int f[110][110],dis[20010];
struct nod{
    int x,s;
    bool operator () (const nod &a,const nod &b){
        return a.s>b.s;
    }
};
int net[4][2]={0,1,1,0,0,-1,-1,0};
vector<nod> g[20010];
priority_queue<nod,vector<nod> ,nod> q;
int get_id(int a,int b){
    if(f[a][b]==0) return (a-1)*m+b;
    else return (a-1)*m+b+m*m;
}
bool vis[100000];
void dij(int qs){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    nod t;
    t.x=qs,t.s=0;
    q.push(t);
    dis[qs]=0;
    while(!q.empty()){
        nod u=q.top();q.pop();
        if(vis[u.x]||u.s>dis[u.x]) continue;
        vis[u.x]=1;
        for(int i=0;i<g[u.x].size();i++){
            nod v=g[u.x][i];
            if(v.s+dis[u.x]<dis[v.x]){
                dis[v.x]=v.s+dis[u.x];
                nod tt;
                tt.x=v.x;
                tt.s=dis[v.x];
                q.push(tt);
            }
        }
    }
    int ans=0x3f3f3f3f;
    ans=min(dis[m+(m-1)*m],dis[2*m+(m-1)*m]);
    if(ans==0x3f3f3f3f) puts("-1");
    else printf("%d",ans);
}
int main(){
    scanf("%d%d",&m,&n);
    // memset(f,-1,sizeof(f));
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=-1;
        }
    }
    for(int i=1;i<=n;i++){
        int x,y,s;
        scanf("%d%d%d",&x,&y,&s);
        f[x][y]=s;
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<4;k++){
                int tx=i+net[k][0],ty=j+net[k][1];
                if(tx<1||ty<1||tx>m||ty>m) continue;
                if(f[i][j]!=-1&&f[tx][ty]!=-1){
                    nod t;
                    t.x=get_id(tx,ty),t.s=(f[i][j]!=f[tx][ty]);
                    g[get_id(i,j)].push_back(t);
                }
                if(f[i][j]==-1&&f[tx][ty]!=-1){
                    nod t;
                    f[i][j]=0;
                    t.x=get_id(tx,ty),t.s=(2+(f[i][j]!=f[tx][ty]));
                    g[get_id(i,j)].push_back(t);
                    f[i][j]=1;
                    t.x=get_id(tx,ty),t.s=(2+(f[i][j]!=f[tx][ty]));
                    g[get_id(i,j)].push_back(t);
                    f[i][j]=-1;
                }
                if(f[i][j]!=-1&&f[tx][ty]==-1){
                    nod t;
                    f[tx][ty]=0;
                    t.x=get_id(tx,ty),t.s=2+(f[i][j]!=f[tx][ty]);
                    g[get_id(i,j)].push_back(t);
                    f[tx][ty]=1;
                    t.x=get_id(tx,ty),t.s=2+(f[i][j]!=f[tx][ty])
                    g[get_id(i,j)].push_back(t);
                    f[tx][ty]=-1;
                }
            }
        }
    }
    dij(get_id(1,1));
    return 0;
}