样例可以过，提交全是MLE咋回事

def dj(start, g):
    num_list = [x for x in range(n) if x != start]
    dis = g[start]
    while len(num_list):
        idx = num_list[0]
        for i in num_list:
            if dis[i] < dis[idx]:
                idx = i
        num_list.remove(idx)
        for i in num_list:
            if dis[idx] + g[idx][i] < dis[i]:
                dis[i] = dis[idx] + g[idx][i]
    return dis

n, m, s = map(int, input().split())
M = 1E100
g = [[M] * n for i in range(n)]
for i in range(len(g)):
    g[i][i] = 0
for i in range(m):
    u, v, w = map(int, input().split())
    g[u - 1][v - 1] = w

res = dj(s - 1, g)
for i in res:
    print(i, end=' ')