#include<bits/stdc++.h>
using namespace std;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},ans=INT_MAX,a[105][105],dp[105][105],n,m;
void dfs(int x,int y,int sum,bool flag){
    if(x<1||y<1||x>m||y>m) return;
    if(sum>=dp[x][y]) return;
    else dp[x][y]=sum;
    if(x==m&&y==m){
        if(sum<ans) ans=sum;
        return;
    }
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(a[nx][ny]){
            if(a[nx][ny]==a[x][y])
				dfs(nx,ny,sum,0);
            else dfs(nx,ny,sum+1,0);
        }
        else{
            if(!flag){
                a[nx][ny]=a[x][y];
                dfs(nx,ny,sum+2,1);
                a[nx][ny]=0;
            }
        }
    }
}
signed main(){
//	freopen("chess.in","r",stdin);
//	freopen("chess.out","w",stdout);
    memset(dp,0x3f,sizeof(dp));
    cin>>m>>n;
    for(int i=1;i<=n;i++){
    	int x,y,c;
        cin>>x>>y>>c;
        c++;
        a[x][y]=c;
    }
    dfs(1,1,0,1);
    if(ans==INT_MAX) cout<<-1;
    else cout<<ans;
    return 0;
}