# Original solution
# Single Source Shortest Path
class node():
    def __init__(self, v, cost):
        self.v = v
        self.cost = cost

infty = 999999999
dict_c = {}
[vertex, edge, r] = list(map(int, input("").split()))
root_c = [node(r, 0)]
final_c = [infty for i in range(vertex)]
final_c[r] = 0

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    if e1 == r:
        root_c.append(node(e2, c))
        final_c[e2] = c
    else:
        dict_c[(e1, e2)] = c

def min_heap(i):
    global root_c
    l = 2*i
    r = 2*i + 1
    if l <= len(root_c) - 1 and root_c[l].cost <= root_c[i].cost:
        if root_c[l].cost < root_c[i].cost:
            min = l
        elif root_c[l].v < root_c[i].v:
            min = l
        else:
            min = i
    else:
        min = i
    if r <= len(root_c) - 1 and root_c[r].cost <= root_c[min].cost:
        if root_c[r].cost < root_c[min].cost:
            min = r
        elif root_c[r].v < root_c[min].v:
            min = r
        #else:

    if min != i:
        root_c[i], root_c[min] = root_c[min], root_c[i]
        min_heap(min)

def build_min_heap():
    global root_c
    length = len(root_c) - 1
    for i in range(int(length/2), 0, -1):
        min_heap(i)

def extract_min():
    global root_c
    min = root_c[1]

    #print("min_cost  ", root_c[1].cost, root_c[2].cost, root_c[3].cost, root_c[4].cost, root_c[5].cost, root_c[6].cost, root_c[7].cost)
    #print("min_vertex", root_c[1].v, root_c[2].v, root_c[3].v, root_c[4].v, root_c[5].v, root_c[6].v, root_c[7].v)

    root_c[1] = root_c[len(root_c) - 1]

    #print("1: ",root_c[1].cost, root_c[1].v)

    del root_c[len(root_c) - 1]
    min_heap(1)

    #print("min_cost  2", root_c[1].cost, root_c[2].cost, root_c[3].cost, root_c[4].cost, root_c[5].cost, root_c[6].cost)
    #print("min_vertex2", root_c[1].v, root_c[2].v, root_c[3].v, root_c[4].v, root_c[5].v, root_c[6].v)
    #print("length: ",len(root_c))

    return min

def decrease_key(i, c):
    global root_c
    root_c[i].cost = c
    while i > 1 and root_c[int(i/2)].cost >= root_c[i].cost:
        if root_c[int(i/2)].cost > root_c[i].cost:
            root_c[int(i/2)], root_c[i] = root_c[i], root_c[int(i/2)]
        elif root_c[int(i/2)].v > root_c[i].v:
            root_c[int(i/2)], root_c[i] = root_c[i], root_c[int(i/2)]
        else:
            root_c[int(i/2)], root_c[i] = root_c[int(i/2)], root_c[i]
        i = int(i/2)

def min_insert(v, c):
    global infty, root_c
    for i in range(1, len(root_c)):
        if root_c[i].v == v:
            decrease_key(i,c)
            return

    root_c.append(node(v, infty))
    decrease_key(len(root_c) - 1, c)

def Dijkstra(root, n):

    count = 1

    global infty, dict_c, root_c, final_c
    label = [i for i in range(n)]

    #print(count, label[root], final_c[label[root]])
    count += 1

    del label[root]

    while len(label) != 0:
        if len(root_c) > 1:
            min_node = extract_min()
        else:
            break

        for i in range(len(label)):
            if min_node.v == label[i]:
                delete_label = i
                continue

            if ((min_node.v, label[i]) in list(dict_c.keys())) == True:
                if final_c[label[i]] > final_c[min_node.v] + dict_c[(min_node.v, label[i])]:
                    final_c[label[i]] = final_c[min_node.v] + dict_c[(min_node.v, label[i])]
                    min_insert(label[i], final_c[label[i]])

        #print(count, label[delete_label], final_c[label[delete_label]])
        count += 1

        del label[delete_label]

build_min_heap()

'''
print("root_c :")
for i in range(len(root_c)):
    print(root_c[i].cost)
print("\n")
'''

Dijkstra(r, vertex)

#print("\n")

for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print((final_c[i]))



# Optimized solution
# Single Source Shortest Path
import heapq

[vertex, edge, r] = list(map(int, input("").split()))
infty = 999999999
final_c = [infty for i in range(vertex)]
dict_c = [[] for i in range(vertex)]

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    dict_c[e1].append((e2, c))

final_c[r] = 0
root_c = [(final_c[r], r)]

def Dijkstra(root, n):
    global infty, root_c, final_c, dict_c, root_c
    while(root_c):
        (cost, v) = heapq.heappop(root_c)
        if cost > final_c[v]:
            continue
        for i in range(len(dict_c[v])):
            (e2, c) = dict_c[v][i]
            if final_c[e2] > final_c[v] + c:
                final_c[e2] = final_c[v] + c
                heapq.heappush(root_c, (final_c[e2], e2))

Dijkstra(r, vertex)
for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print((final_c[i]))