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

d = [float('INF')]*v

d[r] = 0

edges=[]



for i in range(e):

  s,t,c = list(map(int,input().split()))

  edges.append([s,t,c])



for i in range(v):

  count = 0

  for s,v,c in edges:

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

      count += 1

      d[v] = d[s]+c

  if count == 0:

    break



for i in d:

  if i == float('inf'):

    print('INF')

  else:

    print(i)

from heapq import heappush, heappop

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

edges=[[] for i in range(v)]

d = [float('INF')]*v



for i in range(e):

  s,t,c = list(map(int,input().split()))

  edges[s].append([t,c])



que = []

heappush(que,(0,r))

d[r] = 0



while que:

  c, u = heappop(que)

  for v, s in edges[u]:

    if d[v] > s + c:

      d[v] = s + c

      heappush(que,(d[v],v))

for i in d:

  if i == float('inf'):

    print('INF')

  else:

    print(i)

v, e, r = list(map(int, input().split()))
d = [float("INF")] * v
d[r] = 0
edges = []
for i in range(e):
    s, t, c = list(map(int, input().split()))
    edges.append([s, t, c])
for i in range(v):
    count = 0
    for s, v, c in edges:
        if d[v] > d[s] + c:
            count += 1
            d[v] = d[s] + c
    if count == 0:
        break
for i in d:
    if i == float("inf"):
        print("INF")
    else:
        print(i)

from heapq import heappush, heappop

v, e, r = list(map(int, input().split()))
edges = [[] for i in range(v)]
d = [float("INF")] * v
for i in range(e):
    s, t, c = list(map(int, input().split()))
    edges[s].append([t, c])
que = []
heappush(que, (0, r))
d[r] = 0
while que:
    c, u = heappop(que)
    for v, s in edges[u]:
        if d[v] > s + c:
            d[v] = s + c
            heappush(que, (d[v], v))
for i in d:
    if i == float("inf"):
        print("INF")
    else:
        print(i)

+from heapq import heappush, heappop + +edges = [[] for i in range(v)] -d[r] = 0 -edges = [] -    edges.append([s, t, c]) -for i in range(v): -    count = 0 -    for s, v, c in edges: -        if d[v] > d[s] + c: -            count += 1 -            d[v] = d[s] + c -    if count == 0: -        break +    edges[s].append([t, c]) +que = [] +heappush(que, (0, r)) +d[r] = 0 +while que: +    c, u = heappop(que) +    for v, s in edges[u]: +        if d[v] > s + c: +            d[v] = s + c +            heappush(que, (d[v], v))