#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
int m,n,x[1005],y[1005],c[1005],d[1005][1005];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
ll minn=inf;
bool f[1005][1005],flag=false;
inline void dfs(int r,int c,ll ans,int k){
    if(r==m&&c==m){
        minn=min(ans,minn);
        return;
    }
    for(int i=0;i<4;i++){
        int nr=dx[i]+r;
        int nc=dy[i]+c;
        if(1<=nr&&nr<=m&&1<=nc&&nc<=m&&!f[nr][nc]
        &&(d[nr][nc]==1||d[nr][nc]==2)){
            f[nr][nc]=true;
            flag=false;
            if(d[r][c]==0||d[nr][nc]==d[r][c])dfs(nr,nc,ans,k);
            else dfs(nr,nc,ans+1,k);
            f[nr][nc]=false;
        }else if(flag==false&&d[nr][nc]==0){
            k++;
            f[nr][nc]=true;
            flag=true;
            dfs(nr,nc,ans+2,k);
            f[nr][nc]=false;
        }
    }
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x[i],&y[i],&c[i]);
        if(c[i]==1)d[x[i]][y[i]]=1;
        else if(c[i]==0)d[x[i]][y[i]]=2;
    }
    f[1][1]=true;
    dfs(1,1,0,0);
    if(minn>=1&&minn!=inf)printf("%lld\n",minn);
    else if(minn==inf)printf("-1\n");
    return 0;
}