第10个测试点输出为-1

from queue import PriorityQueue

n,m = map(int,input().rstrip().split(" "))
board= [[-1]*(n+1) for _ in range(n+1)]
pointNeedExplore = [[1,0],[0,1]]

for i in range(m):
    x,y,color = map(int,input().rstrip().split(" "))
    board[x][y]=color

def checkpoint(lastColor,x,y,magic)->int:
    if board[x][y]==-1 and magic==1:
        return 2
    elif board[x][y]!=lastColor and board[x][y]!= -1:
        return 1
    elif board[x][y]==lastColor:
        return 0
    elif board[x][y]==-1 and magic == 0:
        return -1


def bfs():
    pq = PriorityQueue()
    visited = set()
    
    # 初始状态：(代价, (x坐标, y坐标), 上一个块的颜色)
    pq.put((0, (1, 1), 1, board[1][1]))
    
    while not pq.empty():
        cost, (x, y), magic, lastColor= pq.get() 
        
        if (x, y, magic) in visited:
            continue
            
        visited.add((x, y, magic))
        
        if x == n and y == n:
            return cost
            
        # 处理相邻位置
        for dx, dy in pointNeedExplore:
            new_x, new_y = x + dx, y + dy
            if 1 <= new_x <= n and 1 <= new_y <= n :
                next_cost = checkpoint(lastColor, new_x, new_y, magic)
                if next_cost == -1 : continue
                if next_cost == 2:
                    next_magic = 0
                    pq.put((next_cost+cost, (new_x, new_y), next_magic, lastColor))
                elif next_cost == 1 or next_cost == 0:
                    next_magic = 1
                    pq.put((next_cost+cost, (new_x, new_y), next_magic, board[new_x][new_y]))
                    
    return -1

ans = bfs()
print(ans)