from collections import defaultdict

import heapq



vertice,edge,source = list(map(int,input().split(" ")))

link = defaultdict(dict)

weight = defaultdict(dict)

answer = [-1] * vertice

for e in range(edge):

    i,j,w = list(map(int,input().split(" ")))

    link[i] = link.get(i,set()) | {j}

    weight[i].update({j:w})

queue = []

heapq.heappush(queue,(0,source))

heapq.heapify(queue)

while queue:

    #print(queue)

    now_cost,here = heapq.heappop(queue)

    #print(now_cost,here,queue)

    if answer[here] > -1:

        continue

    answer[here] = now_cost



    #print(v,here,now_cost,not_went,queue)

    for nw in link[here]:

        if answer[nw] == -1:

            heapq.heappush(queue,(now_cost + weight[here][nw],nw))



for a in answer:

    print((a if a != -1 else "INF"))
import sys

from heapq import heappush, heappop

readline = sys.stdin.readline

from collections import defaultdict

vertices, edges, start = list(map(int, readline().split()))

connect = defaultdict(list)

cost = defaultdict(dict)

answer = ["INF" for n in range(vertices)]

for _ in range(edges):

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

    connect[s].append(t)

    cost[s].update({t:w})

 

 

now = start

weight = 0

p_queue = []

heappush(p_queue, (0, now))

visited = set()

while p_queue:

    weight, now = heappop(p_queue)

    if now in visited:

        continue

    visited |= {now}

    answer[now] = weight

    for c in connect[now]:

        if c not in visited:

            heappush(p_queue, (weight + cost[now][c], c))

for a in answer:

    print(a)

from collections import defaultdict
import heapq

vertice, edge, source = list(map(int, input().split(" ")))
link = defaultdict(dict)
weight = defaultdict(dict)
answer = [-1] * vertice
for e in range(edge):
    i, j, w = list(map(int, input().split(" ")))
    link[i] = link.get(i, set()) | {j}
    weight[i].update({j: w})
queue = []
heapq.heappush(queue, (0, source))
heapq.heapify(queue)
while queue:
    # print(queue)
    now_cost, here = heapq.heappop(queue)
    # print(now_cost,here,queue)
    if answer[here] > -1:
        continue
    answer[here] = now_cost
    # print(v,here,now_cost,not_went,queue)
    for nw in link[here]:
        if answer[nw] == -1:
            heapq.heappush(queue, (now_cost + weight[here][nw], nw))
for a in answer:
    print((a if a != -1 else "INF"))

import sys
from heapq import heappush, heappop

readline = sys.stdin.readline
from collections import defaultdict

vertices, edges, start = list(map(int, readline().split()))
connect = defaultdict(list)
cost = defaultdict(dict)
answer = ["INF" for n in range(vertices)]
for _ in range(edges):
    s, t, w = list(map(int, readline().split()))
    connect[s].append(t)
    cost[s].update({t: w})
now = start
weight = 0
p_queue = []
heappush(p_queue, (0, now))
visited = set()
while p_queue:
    weight, now = heappop(p_queue)
    if now in visited:
        continue
    visited |= {now}
    answer[now] = weight
    for c in connect[now]:
        if c not in visited:
            heappush(p_queue, (weight + cost[now][c], c))
for a in answer:
    print(a)

+import sys +from heapq import heappush, heappop + +readline = sys.stdin.readline -import heapq -vertice, edge, source = list(map(int, input().split(" "))) -link = defaultdict(dict) -weight = defaultdict(dict) -answer = [-1] * vertice -for e in range(edge): -    i, j, w = list(map(int, input().split(" "))) -    link[i] = link.get(i, set()) | {j} -    weight[i].update({j: w}) -queue = [] -heapq.heappush(queue, (0, source)) -heapq.heapify(queue) -while queue: -    # print(queue) -    now_cost, here = heapq.heappop(queue) -    # print(now_cost,here,queue) -    if answer[here] > -1: +vertices, edges, start = list(map(int, readline().split())) +connect = defaultdict(list) +cost = defaultdict(dict) +answer = ["INF" for n in range(vertices)] +for _ in range(edges): +    s, t, w = list(map(int, readline().split())) +    connect[s].append(t) +    cost[s].update({t: w}) +now = start +weight = 0 +p_queue = [] +heappush(p_queue, (0, now)) +visited = set() +while p_queue: +    weight, now = heappop(p_queue) +    if now in visited: -    answer[here] = now_cost -    # print(v,here,now_cost,not_went,queue) -    for nw in link[here]: -        if answer[nw] == -1: -            heapq.heappush(queue, (now_cost + weight[here][nw], nw)) +    visited |= {now} +    answer[now] = weight +    for c in connect[now]: +        if c not in visited: +            heappush(p_queue, (weight + cost[now][c], c)) -    print((a if a != -1 else "INF")) +    print(a)