from heapq import heappush, heappop

V, E, r = list(map(int, input().split()))

inf = 10**10

edges = [[] for _ in [None]*V]

vertices = [inf]*V

vertices[r] = 0



for _ in [None]*E:

    s, t, d = list(map(int, input().split()))

    edges[s].append((t, d))



q = [(0, r)]

rem = V-1

while q:

    cost, v = heappop(q)

    if vertices[v] < cost:

        continue

    for dest, _cost in edges[v]:

        newcost = cost + _cost

        if vertices[dest] > newcost:

            vertices[dest] = newcost

            heappush(q, (newcost, dest))

    rem -= 1

    if rem == 0:

        break



print(("\n".join([str(n) if n!=inf else "INF" for n in vertices])))
import sys

from heapq import heappush, heappop

readline = sys.stdin.readline

V, E, r = list(map(int, readline().split()))

inf = 10**10

edges = [[] for _ in [None]*V]

vertices = [inf]*V

vertices[r] = 0



for _ in [None]*E:

    s, t, d = list(map(int, readline().split()))

    edges[s].append((t, d))



q = [(0, r)]

rem = V-1

while q and rem:

    cost, v = heappop(q)

    if vertices[v] < cost:

        continue

    rem -= 1

    for dest, _cost in edges[v]:

        newcost = cost + _cost

        if vertices[dest] > newcost:

            vertices[dest] = newcost

            heappush(q, (newcost, dest))



print(("\n".join([str(n) if n!=inf else "INF" for n in vertices])))
from heapq import heappush, heappop

V, E, r = list(map(int, input().split()))
inf = 10**10
edges = [[] for _ in [None] * V]
vertices = [inf] * V
vertices[r] = 0
for _ in [None] * E:
    s, t, d = list(map(int, input().split()))
    edges[s].append((t, d))
q = [(0, r)]
rem = V - 1
while q:
    cost, v = heappop(q)
    if vertices[v] < cost:
        continue
    for dest, _cost in edges[v]:
        newcost = cost + _cost
        if vertices[dest] > newcost:
            vertices[dest] = newcost
            heappush(q, (newcost, dest))
    rem -= 1
    if rem == 0:
        break
print(("\n".join([str(n) if n != inf else "INF" for n in vertices])))

import sys
from heapq import heappush, heappop

readline = sys.stdin.readline
V, E, r = list(map(int, readline().split()))
inf = 10**10
edges = [[] for _ in [None] * V]
vertices = [inf] * V
vertices[r] = 0
for _ in [None] * E:
    s, t, d = list(map(int, readline().split()))
    edges[s].append((t, d))
q = [(0, r)]
rem = V - 1
while q and rem:
    cost, v = heappop(q)
    if vertices[v] < cost:
        continue
    rem -= 1
    for dest, _cost in edges[v]:
        newcost = cost + _cost
        if vertices[dest] > newcost:
            vertices[dest] = newcost
            heappush(q, (newcost, dest))
print(("\n".join([str(n) if n != inf else "INF" for n in vertices])))

+import sys -V, E, r = list(map(int, input().split())) +readline = sys.stdin.readline +V, E, r = list(map(int, readline().split())) -    s, t, d = list(map(int, input().split())) +    s, t, d = list(map(int, readline().split())) -while q: +while q and rem: +    rem -= 1 -    rem -= 1 -    if rem == 0: -        break