#include<bits/stdc++.h>
using namespace std;
const int N=110;
bool vis[N][N];
int m,n,a[N][N],sxx,syy,szz,f[N][N][4],xx[6]={1,-1,0,0},yy[6]={0,0,1,-1};
struct node{
    int sx,sy;
};
std::queue<node> q;
void sta()
{
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=-1;
        }
    }
}
void sta2()
{
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]==-1)
            f[i][j][0]=f[i][j][1]=0x3f3f3f3f;
            else
            {
                f[i][j][2]=0x3f3f3f3f;
            }
        }
    }
}
void bfs(int hx,int hy)
{
    if(a[hx][hy]!=-1)
    {
        q.push(node{hx,hy});
        f[hx][hy][a[hx][hy]]=0;
    }
    else
    {
        q.push(node{hx,hy});
        f[hx][hy][1]=2;
        f[hx][hy][0]=2;
    }
    while(!q.empty())
    {
        int x=q.front().sx,y=q.front().sy;
        q.pop();
        vis[x][y]=1;
        for(int i=0;i<4;i++)
        {
            int dx=x+xx[i],dy=y+yy[i];
            if(dx<1||dx>m||dy<1||dy>m)continue;
            if(a[x][y]==-1)
            {
                if(a[dx][dy]==-1)
                {
                    if(f[dx][dy][0]<=f[x][y][0]+2)continue;
                    if(f[dx][dy][1]<=f[x][y][0]+3)continue;
                    if(f[dx][dy][0]<=f[x][y][1]+3)continue;
                    if(f[dx][dy][1]<=f[x][y][1]+2)continue;
                    f[dx][dy][0]=f[x][y][0]+2;
                    f[dx][dy][1]=f[x][y][0]+3;
                    f[dx][dy][0]=f[x][y][1]+3;
                    f[dx][dy][1]=f[x][y][1]+2;
                    q.push(node{dx,dy});
                }
                else
                {
                    if(a[dx][dy]==1)
                    {
                        if(f[dx][dy][2]<=f[x][y][1])continue;
                        if(f[dx][dy][2]<=f[x][y][0]+1)continue;
                        f[dx][dy][2]=f[x][y][1];
                        f[dx][dy][2]=f[x][y][0]+1;
                        q.push(node{dx,dy});
                    }
                    else
                    {
                        if(f[dx][dy][2]<=f[x][y][1]+1)continue;
                        if(f[dx][dy][2]<=f[x][y][0])continue;
                        f[dx][dy][2]=f[x][y][1]+1;
                        f[dx][dy][2]=f[x][y][0];
                        q.push(node{dx,dy});
                    }
                }
            }
            else
            {
                if(a[x][y]==1)
                {
                    if(a[dx][dy]==-1)
                    {
                        if(f[dx][dy][0]<=f[x][y][2]+3)continue;
                        if(f[dx][dy][1]<=f[x][y][2]+2)continue;
                        f[dx][dy][0]=f[x][y][2]+3;
                        f[dx][dy][1]=f[x][y][2]+2;
                        q.push(node{dx,dy});
                    }
                    else
                    {
                        if(a[dx][dy]==1)
                        {
                            if(f[dx][dy][2]<=f[x][y][2])continue;
                            f[dx][dy][2]=f[x][y][2];
                            q.push(node{dx,dy});
                        }
                        else
                        {
                            if(f[dx][dy][2]<=f[x][y][2]+1)continue;
                            f[dx][dy][2]=f[x][y][2]+1;
                            q.push(node{dx,dy});
                        }
                    }
                }
                else
                {
                    if(a[dx][dy]==-1)
                    {
                        if(f[dx][dy][0]<=f[x][y][2]+2)continue;
                        if(f[dx][dy][1]<=f[x][y][2]+3)continue;
                        f[dx][dy][0]=f[x][y][2]+2;
                        f[dx][dy][1]=f[x][y][2]+3;
                        q.push(node{dx,dy});
                    }
                    else
                    {
                        if(a[dx][dy]==1)
                        {
                            if(f[dx][dy][2]<=f[x][y][2]+1)continue;
                            f[dx][dy][2]=f[x][y][2]+1;
                            q.push(node{dx,dy});
                        }
                        else
                        {
                            if(f[dx][dy][2]<=f[x][y][2])continue;
                            f[dx][dy][2]=f[x][y][2];
                            q.push(node{dx,dy});
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    cin>>m>>n;
    sta();
    for(int i=1;i<=n;i++)
    {
        cin>>sxx>>syy>>szz;
        a[sxx][syy]=szz;
    }
    sta2();
    bfs(1,1);
    if(!vis[m][m])
    {
    	cout<<"-1";
    }
    else
    if(a[m][m]==-1)
    {
        cout<<min(f[m][m][0],f[m][m][1]);
    }
    else
    {
        cout<<f[m][m][2];
    }
    return 0;
}