Форд-Беллман

inf = float('inf')
n, m = map(int, input().split())
mx = []
for i in range(m):
    x, y, w = map(int, input().split())
    mx.append((x, y, w))
start = int(input())
w = [inf] * n #w[x] -- кратчайшее расстояние от start до x
w[start] = 0
for _ in range(n):
    for vertex in mx:
        if w[vertex[0]] > w[vertex[1]] + vertex[2]:
            w[vertex[0]] = w[vertex[1]] + vertex[2]
        if w[vertex[1]] > w[vertex[0]] + vertex[2]:
            w[vertex[1]] = w[vertex[0]] + vertex[2]