uVA 929 - получение TLE всегда с использованием кода Python

Question

Я использую алгоритм queue + Dijkstra для решения проблемы, но всегда получаю TLE. Кроме того, я действительно не знаю, как улучшить производительность. Пожалуйста, помогите мне решить эту проблему. Спасибо

ниже мой код:

      import collections

t = int(input())
for _ in range(t):
    n = int(input())
    m = int(input())
    maze = [ list(map(int, input().split())) for _ in range(n)]
    vals  = [ [-1 for _ in range(m)] for _ in range(n)]
    vis  = [ [0 for _ in range(m)] for _ in range(n)]
    vals[0][0] = maze[0][0]

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    pq = collections.deque()
    pq.appendleft((maze[0][0], 0, 0))

    while pq:
        dis, r, c = pq.pop()
        vis[r][c] = 1
        for (mx, my) in directions:
            nx, ny = r+mx, c+my
            if 0<=nx<n and 0<=ny<m and vis[nx][ny]!=1:
                tmp = dis+maze[nx][ny]
                if vals[nx][ny]==-1 or vals[nx][ny]>tmp:
                    vals[nx][ny] = tmp
                    pq.appendleft((tmp, nx, ny))
                
    print(vals[n-1][m-1])