import sys

def bellmanford(G,s):

    n = len(G)

    dist = [float("inf") for i in range(n)]

    dist[s]=0

    for k in range(n):

        flag = False

        for u in range(n):

            for v in range(len(G[u])):

                if dist[G[u][v][0]]>dist[u]+G[u][v][1]:

                    dist[G[u][v][0]]=dist[u]+G[u][v][1]

                    flag = True

        if(not flag):break

    for k in dist:

        if(k==float("inf")):print("INF")

        else:print(k)

                    

                        

def main():

    T =[int(x) for x in sys.stdin.readline().strip().split()]

    V = T[0]

    E = T[1]

    s = T[2]

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

    

    for i in range(E):

        line = [int(x) for x in sys.stdin.readline().strip().split()]

        G[line[0]].append((line[1],line[2]))

    bellmanford(G,s)

main()

    

        



import sys

import heapq

def Dj(G,s):

    n = len(G)

    dist = [float("inf") for i in range(n)]

    vis = [-1 for i in range(n)]

    li = [(0,s)]

    dist[s]=0

    heapq.heapify(li)

    while len(li):

        d,u = heapq.heappop(li)

        if vis[u]==1:

            continue

        vis[u]=1

        for v in G[u]:

            if dist[v[1]]>dist[u] + v[0]:

                dist[v[1]] = dist[u] + v[0]

                heapq.heappush(li,(dist[u] + v[0],v[1]))

    return dist

                

    

    



def main():

    T = [int(x) for x in sys.stdin.readline().strip().split()]

    V = T[0]

    E = T[1]

    S = T[2]

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

    for i in range(E):

        line = [int(x) for x in sys.stdin.readline().strip().split()]

        G[line[0]].append((line[2],line[1]))

    for k in Dj(G,S):

        if k ==float("inf"):print("INF")

        else:print(k)

main()



    

    



import sys


def bellmanford(G, s):
    n = len(G)
    dist = [float("inf") for i in range(n)]
    dist[s] = 0
    for k in range(n):
        flag = False
        for u in range(n):
            for v in range(len(G[u])):
                if dist[G[u][v][0]] > dist[u] + G[u][v][1]:
                    dist[G[u][v][0]] = dist[u] + G[u][v][1]
                    flag = True
        if not flag:
            break
    for k in dist:
        if k == float("inf"):
            print("INF")
        else:
            print(k)


def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    s = T[2]
    G = [[] for i in range(V)]
    for i in range(E):
        line = [int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append((line[1], line[2]))
    bellmanford(G, s)


main()

import sys
import heapq


def Dj(G, s):
    n = len(G)
    dist = [float("inf") for i in range(n)]
    vis = [-1 for i in range(n)]
    li = [(0, s)]
    dist[s] = 0
    heapq.heapify(li)
    while len(li):
        d, u = heapq.heappop(li)
        if vis[u] == 1:
            continue
        vis[u] = 1
        for v in G[u]:
            if dist[v[1]] > dist[u] + v[0]:
                dist[v[1]] = dist[u] + v[0]
                heapq.heappush(li, (dist[u] + v[0], v[1]))
    return dist


def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    S = T[2]
    G = [[] for i in range(V)]
    for i in range(E):
        line = [int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append((line[2], line[1]))
    for k in Dj(G, S):
        if k == float("inf"):
            print("INF")
        else:
            print(k)


main()

+import heapq -def bellmanford(G, s): +def Dj(G, s): +    vis = [-1 for i in range(n)] +    li = [(0, s)] -    for k in range(n): -        flag = False -        for u in range(n): -            for v in range(len(G[u])): -                if dist[G[u][v][0]] > dist[u] + G[u][v][1]: -                    dist[G[u][v][0]] = dist[u] + G[u][v][1] -                    flag = True -        if not flag: -            break -    for k in dist: +    heapq.heapify(li) +    while len(li): +        d, u = heapq.heappop(li) +        if vis[u] == 1: +            continue +        vis[u] = 1 +        for v in G[u]: +            if dist[v[1]] > dist[u] + v[0]: +                dist[v[1]] = dist[u] + v[0] +                heapq.heappush(li, (dist[u] + v[0], v[1])) +    return dist + + +def main(): +    T = [int(x) for x in sys.stdin.readline().strip().split()] +    V = T[0] +    E = T[1] +    S = T[2] +    G = [[] for i in range(V)] +    for i in range(E): +        line = [int(x) for x in sys.stdin.readline().strip().split()] +        G[line[0]].append((line[2], line[1])) +    for k in Dj(G, S): -def main(): -    T = [int(x) for x in sys.stdin.readline().strip().split()] -    V = T[0] -    E = T[1] -    s = T[2] -    G = [[] for i in range(V)] -    for i in range(E): -        line = [int(x) for x in sys.stdin.readline().strip().split()] -        G[line[0]].append((line[1], line[2])) -    bellmanford(G, s) - -