#include<bits/stdc++.h>
using namespace std;
int a[101][101];
int dp[101][101][3];
int get(int x,int y,int nx,int ny){
    int res = 1e9;
    if(a[x][y]){
        res = min(dp[nx][ny][a[x][y]],dp[nx][ny][3-a[x][y]]+1);
    }
    else{
        if(a[nx][ny])dp[x][y][a[nx][ny]] = min(dp[x][y][a[nx][ny]],dp[nx][ny][a[nx][ny]]+2);
    }
    return res;
}
int main(){
    int i,j,m,n,x,y,c;
    scanf("%d%d",&m,&n);
    for(i=0;i<n;++i){
        scanf("%d%d%d",&x,&y,&c);
        if(c==0)a[x][y] = 2;
        else a[x][y] = 1;
    }
    for(i=1;i<=m;++i){
        for(j=1;j<=m;++j){
            for(int k=0;k<3;++k)dp[i][j][k] = 1e9;
        }
    }
    dp[1][1][a[1][1]] = 0;
    for(i=2;i<=m;++i){
        dp[i][1][a[i][1]] = get(i,1,i-1,1);
        dp[1][i][a[1][i]] = get(1,i,1,i-1);
    }
    for(i=2;i<=m;++i){
        for(j=2;j<=m;++j){
            dp[i][j][a[i][j]] = min(get(i,j,i,j-1),get(i,j,i-1,j));
        }    
    }
    int ans = 1e9;
    for(i=0;i<3;++i)ans = min(ans,dp[m][m][i]);
    if(ans==1e9)printf("-1\n");
    else printf("%d\n",ans);
    return 0;
}