import heapq

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

visited = [False] * V

nodes = [[] for i in range(V)]

cost = [[] for i in range(V)]

for i in range(E):

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

    nodes[s].append(t)

    cost[s].append(d)



dist = [float('inf')] * V

dist[root] = 0



h = [(0, root)]

while h:

    c, v = heapq.heappop(h)

    if visited[v]:

        continue

    visited[v] = True

    for i in range(len(nodes[v])):

        t = nodes[v][i]

        if dist[t] > c + cost[v][i]:

            dist[t] = c + cost[v][i]

        if not visited[t]:

            visited[v] = True

            heapq.heappush(h, (c + cost[v][i], t))



for i in range(V):

    if dist[i] == float('inf'):

        print('INF')

    else:

        print((dist[i]))
import heapq

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

visited = [False] * V

nodes = [[] for i in range(V)]

cost = [[] for i in range(V)]

for i in range(E):

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

    nodes[s].append(t)

    cost[s].append(d)



dist = [float('inf')] * V

dist[root] = 0



h = [(0, root)]

while h:

    c, v = heapq.heappop(h)

    if visited[v]:

        continue

    visited[v] = True

    for i in range(len(nodes[v])):

        t = nodes[v][i]

        nc = c + cost[v][i]

        if dist[t] > nc:

            dist[t] = nc

            heapq.heappush(h, (nc, t))



for i in range(V):

    if dist[i] == float('inf'):

        print('INF')

    else:

        print((dist[i]))
import heapq

V, E, root = list(map(int, input().split()))
visited = [False] * V
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s, t, d = list(map(int, input().split()))
    nodes[s].append(t)
    cost[s].append(d)
dist = [float("inf")] * V
dist[root] = 0
h = [(0, root)]
while h:
    c, v = heapq.heappop(h)
    if visited[v]:
        continue
    visited[v] = True
    for i in range(len(nodes[v])):
        t = nodes[v][i]
        if dist[t] > c + cost[v][i]:
            dist[t] = c + cost[v][i]
        if not visited[t]:
            visited[v] = True
            heapq.heappush(h, (c + cost[v][i], t))
for i in range(V):
    if dist[i] == float("inf"):
        print("INF")
    else:
        print((dist[i]))

import heapq

V, E, root = list(map(int, input().split()))
visited = [False] * V
nodes = [[] for i in range(V)]
cost = [[] for i in range(V)]
for i in range(E):
    s, t, d = list(map(int, input().split()))
    nodes[s].append(t)
    cost[s].append(d)
dist = [float("inf")] * V
dist[root] = 0
h = [(0, root)]
while h:
    c, v = heapq.heappop(h)
    if visited[v]:
        continue
    visited[v] = True
    for i in range(len(nodes[v])):
        t = nodes[v][i]
        nc = c + cost[v][i]
        if dist[t] > nc:
            dist[t] = nc
            heapq.heappush(h, (nc, t))
for i in range(V):
    if dist[i] == float("inf"):
        print("INF")
    else:
        print((dist[i]))

-        if dist[t] > c + cost[v][i]: -            dist[t] = c + cost[v][i] -        if not visited[t]: -            visited[v] = True -            heapq.heappush(h, (c + cost[v][i], t)) +        nc = c + cost[v][i] +        if dist[t] > nc: +            dist[t] = nc +            heapq.heappush(h, (nc, t))