//动态规划照亮世界！！！
/*
状态转移方程：
dp[i][j]=INT_MAX-100000  #-100000是为了防止数据溢出
dp[i][j]=min(dp[i][j],dp[ni][nj])  (a[i][j]=a[ni][nj]≠0)
dp[i][j]=min(dp[i][j],dp[ni][nj]+1)  (a[i][j]≠a[ni][nj],a[i][j]≠0,a[ni][nj]≠0)
dp[i][j]=dp[ni][nj]+2,Ls[i][j].x=ni,Ls[i][j].y=nj  (a[i][j]=0,a[ni][nj]≠0,dp[i][j]>dp[ni][nj]+2)  #此次应记录后继
dp[i][j]=min(dp[i][j],dp[ni][nj]+((a[i][j]==a[Ls[ni][nj].x][Ls[ni][nj].y])?0:1))  (a[i][j]≠0,a[ni][nj]=0)
*/
#include<bits/stdc++.h>
using namespace std;
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n,m,a[105][105],dp[105][105];
class Last
{
    public:
        int x,y;
}Ls[105][105];
int main()
{
    cin>>n>>m;
    for(int i=0;i<105;i++)for(int j=0;j<105;j++)dp[i][j]=INT_MAX-100000;
    while(m--)
    {
        int x,y,c;
        cin>>x>>y>>c;
        a[x][y]=c+1;
    }
    dp[1][1]=0;
    for(int xx=1;xx<=n*n/2;xx++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=0;k<4;k++)
                {
                    int ni=i+dir[k][0],nj=j+dir[k][1];
                    if(a[i][j]==a[ni][nj]&&a[i][j]!=0)
                        dp[i][j]=min(dp[i][j],dp[ni][nj]);
                    else if(a[i][j]!=a[ni][nj]&&a[i][j]!=0&&a[ni][nj]!=0)
                        dp[i][j]=min(dp[i][j],dp[ni][nj]+1);
                    else if(a[i][j]==0&&a[ni][nj]!=0&&dp[i][j]>dp[ni][nj]+2)
                    {
                        Ls[i][j].x=ni;Ls[i][j].y=nj;
                        dp[i][j]=dp[ni][nj]+2;
                    }
                    else if(a[i][j]!=0&&a[ni][nj]==0)
                        dp[i][j]=min(dp[i][j],dp[ni][nj]+((a[i][j]==a[Ls[ni][nj].x][Ls[ni][nj].y])?0:1));
                }
    if(dp[n][n]!=INT_MAX-100000) cout<<dp[n][n];
    else cout<<-1<<endl;
    return 0;
}