#include<bits/stdc++.h>
using namespace std;
int x,y,c,m,n,ans=9999999;
int a[101][101];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int flag[101][101];
void dfs(int x,int y,int c,bool f) 
{
    if(x==m && y==m)
    {
        ans=min(c,ans);
        return;
    }
    else
    {
        for(int i=0; i<=3; i++) 
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<=m && tx>=1 && ty<=m && ty>=1 && !flag[tx][ty])
            {
                if(a[tx][ty]==-1)
                {
                    if(f)
                    {
                        a[tx][ty]=a[x][y];
                        flag[tx][ty]=true;
                        dfs(tx,ty,c+2,false);
                        flag[tx][ty]=false;
                        a[tx][ty]=-1;
                    }
                    else
                    {
                        if(a[tx][ty]==a[x][y])
                        {
                            flag[tx][ty]=true;
                            dfs(tx,ty,c,true);
                            flag[tx][ty]=false;
                        }
                        else
                        {
                            flag[tx][ty]=true;
                            dfs(tx,ty,c+1,true);
                            flag[tx][ty]=false;
                        }
                    }
                }
            }
        }
    }
    return;
}
int main()
{
    cin>>m>>n;
    memset(a,-1,sizeof(a));
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>x>>y>>c;
            a[x][y]=c;
        }
    }
    flag[1][1]=true;
    dfs(1,1,0,a[1][1]);
    if(ans==9999999) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}