#include<stdio.h>
#include<limits.h>
struct grid {
    int x,y;
    int color,magic;
    int min_cost;
} grid[100][100];

int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0};
struct grid queue[10000];//存疑

void bfs(int gridSize) {
    int front=0,rear=0;
    queue[rear++]=grid[0][0];
    while(front!=rear) {
        struct grid current=queue[front++];
        //遍历四个方向
        for(int i=0; i<4; i++) {
            int NextX=current.x+dx[i],NextY=current.y+dy[i];
            if(NextX>=gridSize||NextY>=gridSize||NextX<0||NextY<0) continue;
            //相同
            if(current.color==grid[NextX][NextY].color&&current.min_cost<grid[NextX][NextY].min_cost) {
                grid[NextX][NextY].min_cost=current.min_cost;
                queue[rear++]=grid[NextX][NextY];
            }
            //不同
            else if(current.color!=grid[NextX][NextY].color) {
                //后一个节点颜色为0
                if(!current.magic&&grid[NextX][NextY].color==0&&current.min_cost+2<grid[NextX][NextY].min_cost){
                    grid[NextX][NextY].min_cost=current.min_cost+2;
                    queue[rear++]=(struct grid){NextX,NextY,current.color,1,current.min_cost+2};
                }
                //后一个节点颜色不为0
                else if(grid[NextX][NextY].color!=0&&current.min_cost+1<grid[NextX][NextY].min_cost) {
                    grid[NextX][NextY].min_cost=current.min_cost+1;
                    queue[rear++]=grid[NextX][NextY];
                }
            }
        }
    }
}

int main() {
    int gridSize,colorSize;
    scanf("%d%d",&gridSize,&colorSize);
    for(int i=0; i<gridSize; i++)
        for(int j=0; j<gridSize; j++)
            grid[i][j]=(struct grid) {i,j,0,0,INT_MAX};
    grid[0][0].min_cost=0;
    
    for(int i=0; i<colorSize; i++) {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        grid[x-1][y-1].color=c+1;
    }
    bfs(gridSize);
    if(grid[gridSize-1][gridSize-1].min_cost==INT_MAX)
        printf("-1\n");
    else printf("%d\n",grid[gridSize-1][gridSize-1].min_cost);
}