#include <iostream>
#include <cstring>
#include <algorithm>
// #define int long long
using namespace std;
const int N = 1e2+10;
int dist[N][N];
int m,n;
int mapp[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int x,int y,int val,bool mg){
    if(val>=dist[x][y] ){
        return;
    }
    dist[x][y]=val;
    if(x==m && y==m){
        return;
    }
    for (int i = 0; i < 4; i ++ ){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<1 || xx>m || yy<1 || yy>m){
            continue;
        }
        if(mapp[xx][yy]==mapp[x][y]){
            dfs(xx,yy,val,false);
        }
        else if(mapp[xx][yy]!=mapp[x][y] && mapp[xx][yy]!=-1){
            dfs(xx,yy,val+1,false);
        }
        else if(!mg){
            mapp[xx][yy]=mapp[x][y];
            dfs(xx,yy,val+2,true);
            mapp[xx][yy]=-1;
        }
    }
}
signed main()
{
    memset(mapp, -1, sizeof mapp);
    memset(dist,0x3f,sizeof dist);
    cin >> m>>n;
    for (int i = 0; i < n; i ++ ){
        int x,y,num;
        cin >> x>>y>>num;
        mapp[x][y]=num;
    }
    dfs(1,1,0,false);
    if(dist[m][m]==0x3f3f3f3f){
        dist[m][m]=-1;
    }
    cout<<dist[m][m];
    return 0;
}