#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e2 + 10, INF = 3e4;
const int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};

struct node {
  int x, y, f, c, g;
} que[MAXN * MAXN];

int vis[MAXN][MAXN], a[MAXN][MAXN], dp[MAXN][MAXN][2][3];
int n, m, x, y, c, ans = INF, head = 1, tail;

void r(int x, int y, int f, int c, int g) {
  if (x < 1 || x > m || y < 1 || y > m || dp[x][y][f][c] != INF) {
    return ;
  }
  if (x == m && y == m) {
    ans = min(ans, g);
  }
  dp[x][y][f][c] = g;
  que[++tail] = {x, y, f, c, g};
}

void bfs() {
  for (r(1, 1, 0, a[1][1], 0); head <= tail; ) {
    node now = que[head++];
    for (int i = 0; i < 4; i++) {
      int nx = now.x + dx[i], ny = now.y + dy[i];
      if (a[nx][ny]) {
        r(nx, ny, 0, a[nx][ny], now.g + (a[nx][ny] != now.c));
      } else if (!now.f){
        r(nx, ny, 1, a[now.x][now.y], now.g + 2);
      }
    }
  }
}

int main() {
  cin >> m >> n;
  for (int i = 1; i <= n; i++) {
    cin >> x >> y >> c;
    a[x][y] = ++c;
  }
  fill(&vis[1][1], &vis[m][m] + 1, -1);
  fill(&dp[1][1][0][0], &dp[m][m][1][2] + 1, INF);
  bfs();
  cout << (ans == INF ? -1 : ans);
  return 0;
}
// WA on #7 ~ #16, #19 ~ #20