from collections import defaultdict

from heapq import heappush, heappop, heapify

from sys import stdin

def sp(G,R,V):

    d = {}

    q = [(0, R)]

    heapify(q)

    #seen = set()

    while q:

        (cost, v) = heappop(q)

        if v not in d:

            #seen.add(v)

            d[v] = cost

            for (next, c) in list(G[v].items()):

                heappush(q, (cost + c, next))

    return d



V, E, R = [int(x) for x in stdin.readline().split()]

G = defaultdict(dict)

for case in range(E):

    s, t, w = [int(x) for x in stdin

    .readline().split()]

    G[s][t] = w

d = sp(G, R, V)

for k in range(V):

    if k not in d:

        print("INF")

    else:

        print((d[k]))
from collections import defaultdict

from heapq import heappush, heappop, heapify

from sys import stdin

#import time



def sp(G,R,V):

    d = {}

    INF = float('inf')

    for i in range(V):

        d[i] = INF

    q = [(0, R)]

    d[R] = 0

    heapify(q)

    while q:

        (cost, v) = heappop(q)

        for (next, c) in list(G[v].items()):

            if d[next] > d[v] + c:

                d[next] = d[v] + c

                heappush(q, (d[next], next))

    return d



#start = time.clock()



V, E, R = [int(x) for x in stdin.readline().split()]

G = defaultdict(dict)

for case in range(E):

    s, t, w = [int(x) for x in stdin

    .readline().split()]

    G[s][t] = w

d = sp(G, R, V)

for k in range(V):

    if d[k] == float('inf'):

            print("INF")

    else:

        print((d[k]))

#print('Computation time : {}'.format(time.clock()-start))
from collections import defaultdict
from heapq import heappush, heappop, heapify
from sys import stdin


def sp(G, R, V):
    d = {}
    q = [(0, R)]
    heapify(q)
    # seen = set()
    while q:
        (cost, v) = heappop(q)
        if v not in d:
            # seen.add(v)
            d[v] = cost
            for (next, c) in list(G[v].items()):
                heappush(q, (cost + c, next))
    return d


V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict(dict)
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[s][t] = w
d = sp(G, R, V)
for k in range(V):
    if k not in d:
        print("INF")
    else:
        print((d[k]))

from collections import defaultdict
from heapq import heappush, heappop, heapify
from sys import stdin

# import time
def sp(G, R, V):
    d = {}
    INF = float("inf")
    for i in range(V):
        d[i] = INF
    q = [(0, R)]
    d[R] = 0
    heapify(q)
    while q:
        (cost, v) = heappop(q)
        for (next, c) in list(G[v].items()):
            if d[next] > d[v] + c:
                d[next] = d[v] + c
                heappush(q, (d[next], next))
    return d


# start = time.clock()
V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict(dict)
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[s][t] = w
d = sp(G, R, V)
for k in range(V):
    if d[k] == float("inf"):
        print("INF")
    else:
        print((d[k]))
# print('Computation time : {}'.format(time.clock()-start))

- +# import time +    INF = float("inf") +    for i in range(V): +        d[i] = INF +    d[R] = 0 -    # seen = set() -        if v not in d: -            # seen.add(v) -            d[v] = cost -            for (next, c) in list(G[v].items()): -                heappush(q, (cost + c, next)) +        for (next, c) in list(G[v].items()): +            if d[next] > d[v] + c: +                d[next] = d[v] + c +                heappush(q, (d[next], next)) +# start = time.clock() -    if k not in d: +    if d[k] == float("inf"): +# print('Computation time : {}'.format(time.clock()-start))