#include<iostream>
#define MAXN 1001
using namespace std;
int n,m,ans=1e9,sum,mp[1005][1005];
bool vis[1005][1005];
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
const int col[]={0,1};
void dfs(int x,int y,bool magic) {
if(sum>=ans) {
return ;
}
if(x==n&&y==n) {
ans=min(ans,sum);
return ;
}
for(int i=0;i<=3;i++) {
int tx=x+dx[i];
int ty=y+dy[i];
if(tx<=0||tx>n||ty<=0||ty>n||vis[tx][ty]==true) continue;
vis[tx][ty]=true;
if(mp[x][y]==mp[tx][ty]) {
dfs(tx,ty,false);
}
else {
if(mp[tx][ty]!=-1) {
sum++;
dfs(tx,ty,false);
sum--;
}
else {
if(magic==true) continue;
for(int i=0;i<=1;i++) {
mp[tx][ty]=col[i];
sum+=2;
dfs(tx,ty,true);
mp[tx][ty]=-1;
sum-=2;
}
}
}
vis[tx][ty]=false;
}
}
int main() {
vis[1][1]=true;
cin>>n>>m;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
mp[i][j]=-1;
}
}
for(int i=1;i<=m;i++) {
int x,y,color;
cin>>x>>y>>color;
mp[x][y]=color;
}
dfs(1,1,false);
if(ans==1e9) {
cout<<-1<<'\n';
}
else cout<<ans<<'\n';
return 0;
}