output_description: Print the costs of SSSP in the following format.
  
      
      
      c0
      c1
      :
      c|V|-1
      
  
  The output consists of |V| lines. Print the cost of the shortest path from the
  source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the
  source to a vertex, print INF.
input_description: An edge-weighted graph G (V, E) and the source r.
  
      
      
      |V| |E| r
      s0 t0 d0
      s1 t1 d1
      :
      s|E|-1 t|E|-1 d|E|-1
      
  
  |V| is the number of vertices and |E| is the number of edges in G. The graph
  vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the
  source of the graph.
  
  si and ti represent source and target vertices of i-th edge (directed) and di
  represents the cost of the i-th edge.
attempt: # -*- coding: utf-8 -*-
  """
  Created on Sat May 18 23:11:54 2019
  
  @author: maezawa
  """
  
  import collections
  import heapq
  
  
  class Dijkstra:
      def __init__(self):
          self.e = collections.defaultdict(list)
  
      def add(self, u, v, d, directed=False):
          """
          0-indexedでなくてもよいことに注意
          u = from, v = to, d = cost
          directed = Trueなら、有向グラフである
          """
          if directed is False:
              self.e[u].append([v, d])
              self.e[v].append([u, d])
          else:
              self.e[u].append([v, d])
  
      def delete(self, u, v):
          self.e[u] = [_ for _ in self.e[u] if _[0] != v]
          self.e[v] = [_ for _ in self.e[v] if _[0] != u]
  
      def Dijkstra_search(self, s):
          """
          0-indexedでなくてもよいことに注意
          s = 始点
          return: 始点から各点までの最短経路
          """
          d = collections.defaultdict(lambda: float("inf"))
          d[s] = 0
          q = []
          heapq.heappush(q, (0, s))
          v = collections.defaultdict(bool)
          while len(q):
              k, u = heapq.heappop(q)
              if v[u]:
                  continue
              v[u] = True
  
              for uv, ud in self.e[u]:
                  if v[uv]:
                      continue
                  vd = k + ud
                  if d[uv] > vd:
                      d[uv] = vd
                      heapq.heappush(q, (vd, uv))
  
          return d
  
  
  v, e, r = list(map(int, input().split()))
  graph1 = Dijkstra()
  for _ in range(e):
      si, ti, di = list(map(int, input().split()))
      graph1.add(si, ti, di, directed=True)
  
  res = graph1.Dijkstra_search(r)
  for i in range(v):
      ans = res[i]
      if ans == float("inf"):
          print("INF")
      else:
          print(ans)
  
problem_description: Single Source Shortest Path
  
  For a given weighted graph G(V, E) and a source r, find the source shortest
  path to each vertex from the source (SSSP: Single Source Shortest Path).
samples: [{"input": "4 5 0\n    0 1 1\n    0 2 4\n    1 2 2\n    2 3 1\n    1 3 5", "output": "0\n    1\n    3\n    4"}, {"input": "4 6 1\n    0 1 1\n    0 2 4\n    2 0 1\n    1 2 2\n    3 1 1\n    3 2 5", "output": "3\n    0\n    2\n    INF"}]