#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int n,m,a[N][N],v[N][N],k[N][N],d[N][N];
int fx[5]={0,-1,0,1,0},fy[5]={0,0,1,0,-1};
void dfs(int x,int y){
    v[x][y]=1;
    for(int i=1;i<=4;i++){
        int tx=x+fx[i],ty=y+fy[i];
        if(tx<=n&&ty<=n&&tx>=1&&ty>=1&&v[tx][ty]==0){
            v[tx][ty]=1;
            a[tx][ty]=d[tx][ty];
            if(a[tx][ty]==-1&&d[x][y]==-1)continue;
            if(a[tx][ty]==a[x][y]&&a[tx][ty]!=-1&&d[tx][ty]!=-1)k[tx][ty]=min(k[x][y],k[tx][ty]);
            if(a[tx][ty]!=a[x][y]&&a[tx][ty]!=-1&&d[tx][ty]!=-1)k[tx][ty]=min(k[x][y]+1,k[tx][ty]);
            if(a[tx][ty]==-1&&a[x][y]!=-1){
                    k[tx][ty]=min(k[x][y]+2,k[tx][ty]);
                    a[tx][ty]=a[x][y];
            }
            if(tx==n&&ty==n)return;
            //cout<<x<<' '<<y<<"  "<<tx<<' '<<ty<<' '<<k[tx][ty]<<endl;
            dfs(tx,ty);
            v[tx][ty]=0;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	cin>>n>>m;
	int x,y,z;
	memset(a,-1,sizeof(a));
	memset(d,-1,sizeof(d));
	for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            k[i][j]=0x3f3f3f3f;
        }
	}
	for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        a[x][y]=z;
        d[x][y]=z;
	}
	k[1][1]=0;
    dfs(1,1);
    if(k[n][n]==0x3f3f3f3f)cout<<-1;
    else cout<<k[n][n];


    return 0;
}