# include <cstdio> 
# include <iostream>
# include <cstring>
# include <algorithm>
# include <queue>
using namespace std;
const int inf = 1e9;
const int dx[12] = {0,0,-1,1,0,0,-1,-1,-2,1,1,2};
const int dy[12] = {-1,1,0,0,2,-2,1,-1,0,1,-1,0};
const int dw[12] = {0,0,0,0,2,2,2,2,2,2,2,2};
int m,n,x,y,op,map[110][110],ans[110][110];
bool vis[110][110];
struct Node{
    int x,y,w;
};
bool operator < (const Node a,const Node b){
    return a.w>b.w;
}
priority_queue<Node>Q;
void bfs(){
    Q.push((Node){1,1,0});//程序又在这挂了 
    cout << -1;
    
    while(!Q.empty()){
        Node node = Q.top();Q.pop();
        int x = node.x,y = node.y,w = node.w;
        if(!vis[x][y])continue;
        ans[x][y] = w,vis[x][y] = false;
        for(int i= 0 ; i < 12; i++){
            int nx = x+dx[i],ny = y+dy[i],nw = w+dw[i]; 
            if(nx <= 0 || nx > m || ny <= 0 || ny > m || vis[nx][ny] == false || map[nx][ny] == -1) continue;
            if(map[nx][ny] != map[x][y]) Q.push((Node){nx,ny,nw+1});
            else Q.push((Node){nx,ny,nw});   
        }
    } 
}
int main(){
    for(int i= 1; i<= 110;i++) for(int j = 1; j<= 110; j++) map[i][j] =-1,vis[i][j] = true,ans[i][j] = inf;//初始化 
    scanf("%d%d",&m,&n);
    while(n --){
        scanf("%d%d%d",&x,&y,&op);
        map[x][y] = op;
    }
    bfs();
    ans[m][m] = min(ans[m][m],min(ans[m-1][m],ans[m][m-1])+2);
    if(ans[m][m] == inf)printf("-1");
    else printf("%d",ans[m][m]);
}