from heapq import heappop as pop

from heapq import heappush as push



INF = 10 ** 18



class edge:

  def __init__(self, to, cost):

    self.to = to

    self.cost = cost



V, E, r = list(map(int,input().split()))



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

#G[i]...頂点iからの辺、(行き先、コスト)

d = [0 for i in range(V)]

#d[i]...スタートからみた頂点iまでの最短距離



def dijkstra(s, V):

  que = []

  global d

  global G

  d = [INF for i in range(V)]

  d[s] = 0

  push(que, (0,s))



  while len(que):

    p = pop(que)

    v = p[1]

    if (d[v] < p[0]):

      continue

#    print(p)

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

      e = G[v][i]

      if d[e.to] > d[v] + e.cost:

        d[e.to] = d[v] + e.cost

        push(que, (d[e.to], e.to))



for i in range(E):

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

  G[s].append(edge(t,c))

dijkstra(r, V)



for i in range(V):

  if d[i] != INF:

    print((d[i]))

  else:

    print("INF")

from heapq import heappush, heappop



INF = 10 ** 20



v_num, e_num, r = list(map(int, input().split()))

edges_lst = [[] for _ in range(v_num)]

dist_lst = [INF for _ in range(v_num)]



for _ in range(e_num):

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

  edges_lst[s].append((t, dist))



que = []

heappush(que, (0, r))

dist_lst[r] = 0



while que:

  dist, node = heappop(que)

  for to, cost in edges_lst[node]:

    if dist_lst[to] > cost + dist:

      dist_lst[to] = cost + dist

      heappush(que, (cost + dist, to))



for dist in dist_lst:

  if dist == INF:

    print("INF")

  else:

    print(dist)



from heapq import heappop as pop
from heapq import heappush as push

INF = 10**18


class edge:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


V, E, r = list(map(int, input().split()))
G = [[] for i in range(V)]
# G[i]...頂点iからの辺、(行き先、コスト)
d = [0 for i in range(V)]
# d[i]...スタートからみた頂点iまでの最短距離
def dijkstra(s, V):
    que = []
    global d
    global G
    d = [INF for i in range(V)]
    d[s] = 0
    push(que, (0, s))
    while len(que):
        p = pop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        #    print(p)
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                push(que, (d[e.to], e.to))


for i in range(E):
    s, t, c = list(map(int, input().split()))
    G[s].append(edge(t, c))
dijkstra(r, V)
for i in range(V):
    if d[i] != INF:
        print((d[i]))
    else:
        print("INF")

from heapq import heappush, heappop

INF = 10**20
v_num, e_num, r = list(map(int, input().split()))
edges_lst = [[] for _ in range(v_num)]
dist_lst = [INF for _ in range(v_num)]
for _ in range(e_num):
    s, t, dist = list(map(int, input().split()))
    edges_lst[s].append((t, dist))
que = []
heappush(que, (0, r))
dist_lst[r] = 0
while que:
    dist, node = heappop(que)
    for to, cost in edges_lst[node]:
        if dist_lst[to] > cost + dist:
            dist_lst[to] = cost + dist
            heappush(que, (cost + dist, to))
for dist in dist_lst:
    if dist == INF:
        print("INF")
    else:
        print(dist)

-from heapq import heappop as pop -from heapq import heappush as push +from heapq import heappush, heappop -INF = 10**18 - - -class edge: -    def __init__(self, to, cost): -        self.to = to -        self.cost = cost - - -V, E, r = list(map(int, input().split())) -G = [[] for i in range(V)] -# G[i]...頂点iからの辺、(行き先、コスト) -d = [0 for i in range(V)] -# d[i]...スタートからみた頂点iまでの最短距離 -def dijkstra(s, V): -    que = [] -    global d -    global G -    d = [INF for i in range(V)] -    d[s] = 0 -    push(que, (0, s)) -    while len(que): -        p = pop(que) -        v = p[1] -        if d[v] < p[0]: -            continue -        #    print(p) -        for i in range(len(G[v])): -            e = G[v][i] -            if d[e.to] > d[v] + e.cost: -                d[e.to] = d[v] + e.cost -                push(que, (d[e.to], e.to)) - - -for i in range(E): -    s, t, c = list(map(int, input().split())) -    G[s].append(edge(t, c)) -dijkstra(r, V) -for i in range(V): -    if d[i] != INF: -        print((d[i])) +INF = 10**20 +v_num, e_num, r = list(map(int, input().split())) +edges_lst = [[] for _ in range(v_num)] +dist_lst = [INF for _ in range(v_num)] +for _ in range(e_num): +    s, t, dist = list(map(int, input().split())) +    edges_lst[s].append((t, dist)) +que = [] +heappush(que, (0, r)) +dist_lst[r] = 0 +while que: +    dist, node = heappop(que) +    for to, cost in edges_lst[node]: +        if dist_lst[to] > cost + dist: +            dist_lst[to] = cost + dist +            heappush(que, (cost + dist, to)) +for dist in dist_lst: +    if dist == INF: +        print("INF") -        print("INF") +        print(dist)