#include <bits/stdc++.h>
#define int long long
using namespace std ;
int n , m , x , y , c , a[105][105] , minn = LONG_LONG_MAX ;
bool f , vis[105][105] ;
int dx[4] = {1 , 0 , -1 , 0} ;
int dy[4] = {0 , 1 , 0 , -1} ;
void dfs(int lx , int ly , int x , int y , int sum)
{
    if(x == n && y == n)
    {
        minn = min(minn , sum) ;
        f = 1 ;
        return ;
    }
    vis[x][y] = 1 ;
    if(a[x][y] == 0)
    {
        bool fl = 0 ;
        for(int i = 0 ; i < 4 ; i++)
        {
            int nx = x + dx[i] ;
            int ny = y + dy[i] ;
            if(nx < 1 || nx > n || ny < 1 || ny > n)    continue ;
            if(vis[nx][ny])	continue ;
            if(!a[nx][ny])  continue ;
            fl = 1 ;
            if(a[lx][ly] == a[nx][ny])  dfs(x , y , nx , ny , sum) ;
            else    dfs(x , y , nx , ny , sum + 1) ;
        }
        if(!fl) return ;
    }
    else
    {
        for(int i = 0 ; i < 4 ; i++)
        {
            int nx = x + dx[i] ;
            int ny = y + dy[i] ;
            if(nx < 1 || nx > n || ny < 1 || ny > n)    continue ;
			if(vis[nx][ny])	continue ;
            if(!a[nx][ny])  dfs(x , y , nx , ny , sum + 2) ;
            else
            {
                if(a[nx][ny] == a[x][y])    dfs(x , y , nx , ny , sum) ;
                else    dfs(x , y , nx , ny , sum + 1) ;
            }
        }
    }
    vis[x][y] = 0 ;
}
signed main()
{
    cin >> n >> m ;
    while(m--)
    {
        cin >> x >> y >> c ;
        if(c == 0)  c = 2 ;
        a[x][y] = c ;
    }
    dfs(0 , 0 , 1 , 1 , 0) ;
    if(!f)  cout << -1 ;
    else    cout << minn ;
    return 0 ;
}