#include<cstdio>

 #include<cstring>

 #include<iostream>

 using namespace std;

 int n, m, ans = 0x7ffffff;

 int dir[][] = {{, }, {-, }, {, -}, {, }};

 int mp[][], dp[][];

 inline void dfs(int x, int y, int sum, bool magic){

     if(x <  || y <  || x > m || y > m) return;

     if(sum >= dp[x][y]) return;//记忆化剪枝

     dp[x][y] = sum;

     if(x == m && y == m) {ans = min(ans, sum); return;}

     for(int i = ; i < ; i++){

         int nx = x + dir[i][];

         int ny = y + dir[i][];

         if(nx <  || ny <  || nx > m || ny > m) continue;

         if(mp[nx][ny]){

             if(mp[x][y] == mp[nx][ny]) dfs(nx, ny, sum, );

             else dfs(nx, ny, sum+, );

         }

         else{

             if(!magic){

                 mp[nx][ny] = mp[x][y];

                 dfs(nx, ny, sum+, );

                 mp[nx][ny] = ;

             }//处理魔法，注意回溯

         }

     }

 }

 int main(){

     memset(dp, 0x3f3f3f, sizeof(dp));

     scanf("%d%d", &m, &n);

     for(int i = ; i <= n; i++){

         int x, y, c;

         scanf("%d%d%d", &x, &y, &c);

         mp[x][y] = c + ;

         //无色-0

     }

     dfs(, , , );

     printf("%d", ans == 0x7ffffff ? - : ans);

     return ;

 }