include

include

using namespace std; int t[110][110][3],v = 100000000; int p[110][110]; int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1}; struct t3{ int x,y,s,c; }a[1000001]; int main(){

int nx,ny,ns,n,m,f,r,ans=v; cin >> m >> n; for(int i = 1; i <= n; i++){

cin >> nx >> ny >> ns;
p[nx][ny] = ns + 1;

} for(int i = 1; i <= m; i++)

for(int j = 1; j <= m; j++)
  t[i][j][0] = t[i][j][1] = t[i][j][2] = v;

f = 1,r = 1; a[1].x = 1; a[1].y = 1; t[1][1][p[1][1]] = 0; a[1].c = p[1][1]; a[1].s = 0; while(f <= r){

if(ans < a[f].s){
  f++;
  continue;
}
for(int i = 0; i < 4; i++){
  nx = a[f].x + dx[i];
  ny = a[f].y + dy[i];
  if(nx > 0 && nx <= m && ny > 0 && ny <= m){
    if (p[nx][ny] == 0){
      if (p[a[f].x][a[f].y] != 0){
        ns = a[f].s + 2;
        if (a[f].c != 1) ns++;
        if (ns < t[nx][ny][1]){
          if (nx == m && ny == m && ans > ns)  ans = ns;
          else{
            r++;
            a[r].c = 1;
            a[r].x = nx;
            a[r].y = ny;
            a[r].s = ns;
            t[nx][ny][1] = ns;
          }
        }
        ns = a[f].s + 2;
        if (a[f].c != 2) ns++;
        if (ns < t[nx][ny][2]) {
          if(nx == m && ny == m && ans > ns)  ans = ns;
          else{
            r++;
            a[r].c = 2;
            a[r].x = nx;
            a[r].y = ny;
            a[r].s = ns;
            t[nx][ny][2] = ns;
          }
        }
      }
    }else{
      ns = a[f].s;
      if(p[nx][ny] != a[f].c) ns++;
      if(ns < t[nx][ny][p[nx][ny]]){
        if(nx == m && ny == m && ans > ns)  ans = ns;
        else{
          r++;
          a[r].c = p[nx][ny];
          a[r].x = nx;
          a[r].y = ny;
          a[r].s = ns;
          t[nx][ny][p[nx][ny]] = ns;
        }
      }
     }
  }
}
++f;

} if(ans != v) cout << ans << endl; else if(m==1&&n==1)cout<<0; else cout<<-1; return 0; }