这道题还是用dfs简单，我尝试写了下bfs版本的，用以熟悉bfs。

用bfs的话，务必要考虑下把哪些元素入队。
这里我们需要把坐标和颜色值以及金币花销入队。
请务必注意金币花销入队的原因，用以更新nx，ny的花销（nx,ny表示当前点扩展到的点）

from collections import deque

m, n = map(int, input().split())

g = [[-1] * (m) for i in range(m)]
for i in range(n):
    a, b, c = map(int, input().split())
    g[a - 1][b - 1] = c

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
    cost = [[0x3f3f] * m for i in range(m)]
    q = deque()
    q.append((0, 0, g[0][0], 0))
    cost[0][0] = 0
    while len(q):
        x, y, color, w= q.popleft()
        for i in range(4):
            nx, ny= x + dx[i], y + dy[i]
            if nx < 0 or nx >= m or ny < 0 or ny >= m: continue
            tmp = g[nx][ny]
            if tmp == -1 and g[x][y] == -1: continue
            if color == tmp:
                if cost[nx][ny] > w:
                    cost[nx][ny] = w
                    q.append((nx, ny, color, w))
            if color != tmp:
                if tmp != -1:
                    if cost[nx][ny] > w + 1:
                        cost[nx][ny] = w + 1
                        q.append((nx, ny, tmp, w + 1))
                if tmp == -1:
                    if cost[nx][ny] > w + 2:
                        cost[nx][ny] = w + 2
                        q.append((nx, ny, color, w + 2))
    print(cost[m - 1][m - 1]) if cost[m - 1][m - 1] != 0x3f3f else print(-1)
bfs()