rt

#include<bits/stdc++.h>
using namespace std;
int m, n, x, y, c;
int graph[110][110];
int ans = 0x7fffffff, f;
int fx[4] = {-1, 0, 1, 0};
int fy[4] = {0, -1, 0, 1};
void dfs(int x,int y,int sum,int t){
    if(x <= 0 || y <= 0 || x > m || y > m) return;
    if(x==m&&y==m){
        f = 1;
        if(sum<ans)
            ans = sum;
        return;
    }
    int x2, y2;
    for (int i = 0; i < 4;i++){
        x2 += fx[i];
        y2 += fy[i];
        if(graph[x2][y2]!=-1){
            if(graph[x2][y2]==graph[x][y])
                dfs(x2, y2, sum, 1);
            else dfs(x2, y2, sum + 1, 1);
        }
        else{
            if(t==1){
                graph[x2][y2] = graph[x][y];
                dfs(x2, y2, sum + 2, 0);
                graph[x2][y2] = -1;
            }
        }
    }
}
int main(){
    scanf("%d%d", &m, &n);
    memset(graph, -1, sizeof(graph));
    for (int i = 1; i <= n;i++){
        scanf("%d%d%d", &x, &y, &c);
        graph[x][y] = c;
    }
    dfs(1, 1, 0, 1);
    if(f==0){
        printf("-1");
        system("pause");
        return 0;
    }
    printf("%d", ans);
    system("pause");
    return 0;
}