import heapq



maxd = float('inf')

nv, ne, r = [int(n) for n in input().split(' ')]

vertices = {k: {} for k in range(nv)}

for i in range(ne):

    s, t, w = [int(n) for n in input().split(' ')]

    vertices[s][t] = w



q = []

heapq.heappush(q, (0, r))



dist = {v: maxd for v in vertices}

dist[r] = 0



while len(q):

    u = heapq.heappop(q)[1]



    for v in vertices[u]:

        alt = dist[u] + vertices[u][v]

        if alt < dist[v]:

            dist[v] = alt

            heapq.heappush(q, (alt, v))



[print(d) if d < maxd else print("INF") for v, d in dist.items()]

import heapq



nv, ne, r = map(int, input().split(' '))

vertices = [[] for i in range(nv)]

for i in range(ne):

    s, t, w = map(int, input().split(' '))

    vertices[s].append((t, w))



q = []

heapq.heappush(q, (0, r))



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

dist[r] = 0



while len(q):

    u = heapq.heappop(q)[1]



    for t, w in vertices[u]:

        alt = dist[u] + w

        if alt < dist[t]:

            dist[t] = alt

            heapq.heappush(q, (alt, t))



[print(d) if d < float('inf') else print("INF") for d in dist]

import heapq

maxd = float("inf")
nv, ne, r = [int(n) for n in input().split(" ")]
vertices = {k: {} for k in range(nv)}
for i in range(ne):
    s, t, w = [int(n) for n in input().split(" ")]
    vertices[s][t] = w
q = []
heapq.heappush(q, (0, r))
dist = {v: maxd for v in vertices}
dist[r] = 0
while len(q):
    u = heapq.heappop(q)[1]
    for v in vertices[u]:
        alt = dist[u] + vertices[u][v]
        if alt < dist[v]:
            dist[v] = alt
            heapq.heappush(q, (alt, v))
[print(d) if d < maxd else print("INF") for v, d in dist.items()]

import heapq

nv, ne, r = map(int, input().split(" "))
vertices = [[] for i in range(nv)]
for i in range(ne):
    s, t, w = map(int, input().split(" "))
    vertices[s].append((t, w))
q = []
heapq.heappush(q, (0, r))
dist = [float("inf")] * nv
dist[r] = 0
while len(q):
    u = heapq.heappop(q)[1]
    for t, w in vertices[u]:
        alt = dist[u] + w
        if alt < dist[t]:
            dist[t] = alt
            heapq.heappush(q, (alt, t))
[print(d) if d < float("inf") else print("INF") for d in dist]

-maxd = float("inf") -nv, ne, r = [int(n) for n in input().split(" ")] -vertices = {k: {} for k in range(nv)} +nv, ne, r = map(int, input().split(" ")) +vertices = [[] for i in range(nv)] -    s, t, w = [int(n) for n in input().split(" ")] -    vertices[s][t] = w +    s, t, w = map(int, input().split(" ")) +    vertices[s].append((t, w)) -dist = {v: maxd for v in vertices} +dist = [float("inf")] * nv -    for v in vertices[u]: -        alt = dist[u] + vertices[u][v] -        if alt < dist[v]: -            dist[v] = alt -            heapq.heappush(q, (alt, v)) -[print(d) if d < maxd else print("INF") for v, d in dist.items()] +    for t, w in vertices[u]: +        alt = dist[u] + w +        if alt < dist[t]: +            dist[t] = alt +            heapq.heappush(q, (alt, t)) +[print(d) if d < float("inf") else print("INF") for d in dist]