rt

#include<bits/stdc++.h>
using namespace std;
int mp[110][110],vis[110][110],a[110][110];
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
int n,m,hh,tt;
struct node{
    int x,y,co,fl,w;
    bool operator <(const node &W)const{
    	return w>W.w;
    }
};
priority_queue<node>q;
void bfs(int sx,int sy,int c){
    q.push({sx,sy,c,0,0});
    vis[sx][sy]=1;
    while(!q.empty()){
        int x=q.top().x,y=q.top().y,cc=q.top().co,f=q.top().fl,w=q.top().w;
        q.pop();
        for(int i=1;i<=4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx<=n&&xx>0&&yy<=n&&yy>0&&!vis[xx][yy]){
                if(mp[xx][yy]==-1){//走到的点无色 
                    if(!f){
                        if(cc==1){
                            a[xx][yy]=min(a[xx][yy],w+2);
                            q.push({xx,yy,1,1,a[xx][yy]});
                        }else{
                            a[xx][yy]=min(a[xx][yy],w+2);
                            q.push({xx,yy,0,1,a[xx][yy]});
                        }
                        vis[xx][yy]=1;
                    }else{
                        vis[xx][yy]=1;
                    }
                }else{
                    if(mp[xx][yy]!=cc){
                        a[xx][yy]=min(a[xx][yy],w+1);
                        q.push({xx,yy,mp[xx][yy],0,a[xx][yy]});
                        vis[xx][yy]=1;
                    }else{
                        a[xx][yy]=min(a[xx][yy],w);
                        q.push({xx,yy,mp[xx][yy],0,a[xx][yy]});
                        vis[xx][yy]=1;
                    }
                }
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(mp,-1,sizeof mp);
    memset(a,0x3f3f3f,sizeof a);
    for(int i=1;i<=m;i++){
        int x,y,c;
        cin>>x>>y>>c;
        mp[x][y]=c;
    }
    a[1][1]=0;
    bfs(1,1,mp[1][1]);
    if(a[n][n]>0x3f3f00){
        cout<<-1;
        return 0;
    }
    cout<<a[n][n]<<"\n";
    return 0;
}