#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1e2 + 10;

struct Node
{
    int x;
    int y;
    int color;
    int val;
    Node(int tx, int ty, int tcolor, int tval)
    {
        x = tx;
        y = ty;
        color = tcolor;
        val = tval;
    }
};

int nums[105][105];
int cost[105][105];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

int ifout(int nx, int ny, int n)
{
    if(nx < 1 
	|| nx > n 
    || ny < 1 
	|| ny > n)
    {
        return 1;
    }
	else
	{
		return 0;
	}
} 

int bfs(int x, int y, int n)
{
    int ans = 0x3f3f3f3f;
    queue<Node> qlist;
    
    int total = 0;
    int nx = 0, ny = 0;
    Node tnode(x, y, nums[x][y], 0);
    
    qlist.push(tnode);
    cost[1][1] = 0;

    while(!qlist.empty())
    {
        tnode = qlist.front();
        qlist.pop();

        if(tnode.val > ans)
        {
            continue;
        }

        if(tnode.x == n && tnode.y == n)
        {
            ans = min(ans,tnode.val);
            continue;
        }

        for(int i = 0;i < 4;i++)
        {
            nx = tnode.x + dx[i];
            ny = tnode.y + dy[i];

            if(ifout(nx, ny, n) == 1)
            {
                continue;
            }

            if(nums[tnode.x][tnode.y] > 0
			&& nums[nx][ny] > 0
			&& nums[tnode.x][tnode.y] == nums[nx][ny])
            {
                if(total >= cost[nx][ny])
                {
                    continue;
                }
                qlist.push((Node){nx,ny,nums[nx][ny],total});
                cost[nx][ny] = total;
            }

            if(nums[tnode.x][tnode.y] > 0 
			&& nums[nx][ny] > 0
			&& nums[tnode.x][tnode.y] != nums[nx][ny])
            {
                total = tnode.val + 1;
                if(total >= cost[nx][ny])
                {
                    continue;
                }
                qlist.push((Node){nx, ny, nums[tnode.x][tnode.y],total});
                cost[nx][ny] = total;
            }
            
            if(nums[tnode.x][tnode.y] > 0
			&& nums[nx][ny] == 0)
			{
				total = tnode.val + 2;
				if(total >= cost[nx][ny])
				{
					continue;
				}
				qlist.push((Node){nx,ny,nums[tnode.x][tnode.y],total});
				cost[nx][ny] = total;
			}
			
            if(nums[tnode.x][tnode.y] == 0 && nums[nx][ny] > 0)
            {
                if(tnode.color != nums[nx][ny])
                {
                	total = tnode.val + 1;
                }
                if(total >= cost[nx][ny])
                {
                	continue;
                }
                qlist.push((Node){nx,ny,nums[tnode.x][tnode.y],total});
                cost[nx][ny] = total;
            }
        }
    }
	if(ans == 0x3f3f3f3f)
	{
		return -1;
	}
	else
	{
		return ans;
	}
}

int main() 
{
    int n = 0,m = 0;
    int x = 0, y = 0,c = 0;
    int res = 0;
    memset(cost,0x3f,sizeof(cost));
    cin >> n >> m;
    for(int i = 0;i < m;i++)
    {
        cin >> x >> y >> c;
        nums[x][y] = c + 1;
    }

    res = bfs(1,1,n);
    
    cout << res << endl;
    return 0;
}