#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 1010
#define INF 1e6
using namespace std;
int m,n;
int mapp[N][N];
int vis[N][N];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
void dfs(int x,int y)
{
    if(vis[x][y]>vis[m][m]) return;
    for(int i=0;i<4;i++)
    {
        int ax = x + dx[i];
        int ay = y + dy[i];
        if(ax>=1&&ax<=m&&ay>=1&&ay<=m)
        {
            if(!mapp[ax][ay] && vis[x][y]+2 < vis[ax][ay] && mapp[x][y]) 
            {
                vis[ax][ay] = vis[x][y] + 2;
                dfs(ax,ay);
            }
            if((mapp[ax][ay] == mapp[x][y])&& vis[x][y] < vis[ax][ay])
            {
                vis[ax][ay] = vis[x][y];
                dfs(ax,ay);
            }
           if((mapp[ax][ay] != mapp[x][y]) && vis[x][y]+1 < vis[ax][ay])
            {
                vis[ax][ay] = vis[x][y]+1;
                dfs(ax,ay);
            }
        }
    }
}
int main()
{
    memset(vis,INF,sizeof(vis));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        mapp[x][y] = c+1;
    }
    vis[1][1] = 0;
    dfs(1,1);
    if(vis[m][m] == INF) cout<<"-1"<<endl;
    else cout<<vis[m][m]<<endl;
    return 0;
}

样例过不了，不知道哪错了...