v,e,s=list(map(int,input().split()))

edge=[]

inf =1000000100

for i in range(v):

    edge.append([])



for i in range(e):

    vs,vt,d=list(map(int,input().split()))

    edge[vs].append((vt,d))

    

dis=[]

for i in range(v):

    dis.append(inf)



dis[s]=0



for j in range(v):

    update=False

    for i in range(v):

        for (t,d) in edge[i]:

            if dis[i]<inf and d<inf and dis[t]>dis[i]+d:

                dis[t]=dis[i]+d

                update=True

    if update==False: break



for i in range(v):

    if dis[i]>=inf:

        print("INF")

    else:

        print((dis[i]))

            
'''

????????£????????????????????????



'''



import queue

v,e,s=list(map(int,input().split()))

edge=[]

inf =1000000100

for i in range(v):

    edge.append([])



for i in range(e):

    vs,vt,d=list(map(int,input().split()))

    edge[vs].append((vt,d))

    

dis=[]

for i in range(v):

    dis.append(inf)



dis[s]=0



q = queue.PriorityQueue()

q.put((0,s))



while(not q.empty()):

    now=q.get()

#    print("get",now)

    nowv=now[1]

    for (vt,d) in edge[nowv]:

        if dis[vt]>dis[nowv]+d:

            dis[vt]=dis[nowv]+d

            q.put((dis[vt],vt))

#            print("put",(dis[vt],vt))



    

for i in range(v):

    if dis[i]>=inf:

        print("INF")

    else:

        print((dis[i]))
v, e, s = list(map(int, input().split()))
edge = []
inf = 1000000100
for i in range(v):
    edge.append([])
for i in range(e):
    vs, vt, d = list(map(int, input().split()))
    edge[vs].append((vt, d))
dis = []
for i in range(v):
    dis.append(inf)
dis[s] = 0
for j in range(v):
    update = False
    for i in range(v):
        for (t, d) in edge[i]:
            if dis[i] < inf and d < inf and dis[t] > dis[i] + d:
                dis[t] = dis[i] + d
                update = True
    if update == False:
        break
for i in range(v):
    if dis[i] >= inf:
        print("INF")
    else:
        print((dis[i]))

"""
????????£????????????????????????
"""
import queue

v, e, s = list(map(int, input().split()))
edge = []
inf = 1000000100
for i in range(v):
    edge.append([])
for i in range(e):
    vs, vt, d = list(map(int, input().split()))
    edge[vs].append((vt, d))
dis = []
for i in range(v):
    dis.append(inf)
dis[s] = 0
q = queue.PriorityQueue()
q.put((0, s))
while not q.empty():
    now = q.get()
    #    print("get",now)
    nowv = now[1]
    for (vt, d) in edge[nowv]:
        if dis[vt] > dis[nowv] + d:
            dis[vt] = dis[nowv] + d
            q.put((dis[vt], vt))
#            print("put",(dis[vt],vt))
for i in range(v):
    if dis[i] >= inf:
        print("INF")
    else:
        print((dis[i]))

+""" +????????£???????????????????????? +""" +import queue + -for j in range(v): -    update = False -    for i in range(v): -        for (t, d) in edge[i]: -            if dis[i] < inf and d < inf and dis[t] > dis[i] + d: -                dis[t] = dis[i] + d -                update = True -    if update == False: -        break +q = queue.PriorityQueue() +q.put((0, s)) +while not q.empty(): +    now = q.get() +    #    print("get",now) +    nowv = now[1] +    for (vt, d) in edge[nowv]: +        if dis[vt] > dis[nowv] + d: +            dis[vt] = dis[nowv] + d +            q.put((dis[vt], vt)) +#            print("put",(dis[vt],vt))