#include<bits/stdc++.h>

using namespace std;

int m,n;

int clor[][],money[][];

//clor是记录颜色的数组 ，0无色，1红色，2黄色

//money是记录走到(x,y)的最少花费

int dx[]={-,,,},dy[]={,-,,};

int x,y,c;

bool flag=;  //判断有无解 

bool pan(int x,int y)

{

    return x>=&&x<=m&&y>=&&y<=m;

}

void dfs(int x,int y,int step,bool use)

//走到了(x,y),话费为step，use表示是否使用了魔法

{

    if(!pan(x,y)) return;  //不合法直接退出

    if(step>=money[x][y]) return ;
    //最小值判断

    //如果走到(x,y)的花费比之前搜到的结果还大，那么直接退出

    money[x][y]=step;

    //更新成更小花费

    if(x==m&&y==m)

    {

        flag=;

        return;

    }//有解

    for(int i=;i<=;i++)  //四连通深搜

    {

        int xx=x+dx[i],yy=y+dy[i];

        if(pan(xx,yy))  //新节点合法

        {

            if(clor[xx][yy]!=) //新节点有颜色

            {

                if(clor[xx][yy]==clor[x][y]) //新节点与原来节点同色

                    dfs(xx,yy,step,);

                else  //新节点与原来节点不同色

                    dfs(xx,yy,step+,);

            }

            else if(!use)  //新节点无色，没有使用过魔法，可以使用魔法

            {

                clor[xx][yy]=clor[x][y]; //暂时变色

                dfs(xx,yy,step+,);

                clor[xx][yy]=;  //回溯

            }

        }

    }

}

int main()

{

    scanf("%d%d",&m,&n);

    memset(money,0x3f,sizeof(money));  //初始化极大值

    for(int i=;i<=n;i++)

    {

        scanf("%d%d%d",&x,&y,&c);

        clor[x][y]=c+;

    }

    dfs(,,,);

    if(flag==)

    {

        printf("%d\n",money[m][m]);

    }

    else

    {

        printf("-1\n");

    }

    return ;

}