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: #!/usr/bin/env python
  # -*- coding: utf-8 -*-
  
  """
  input:
  4 6 1
  0 1 1
  0 2 4
  2 0 1
  1 2 2
  3 1 1
  3 2 5
  
  output:
  3
  0
  2
  INF
  """
  
  import sys
  import heapq as hp
  from math import isinf
  
  WHITE, GRAY, BLACK = 0, 1, 2
  
  
  def generate_adj_table(v_table):
      for each in v_table:
          source, target, cost = map(int, each)
          init_adj_table[source][target] = cost
      return init_adj_table
  
  
  def dijkstra_path_heap():
      # path search init
      distance[root] = 0
      path_heap = []
      # heapq: rank by tuple[0], at here it's d[u]
      hp.heappush(path_heap, (0, root))
  
      while path_heap:
          current = hp.heappop(path_heap)[1]
  
          color[current] = BLACK
  
          for adj, cost in adj_table[current].items():
              if color[adj] is not BLACK:
                  # alt: d[u] + w[u,v]
                  alt_path = distance[current] + cost
                  if alt_path < distance[adj]:
                      # update path_list
                      distance[adj] = alt_path
                      # update heap
                      hp.heappush(path_heap, (alt_path, adj))
                      color[adj] = GRAY
                      parents[adj] = current
  
      return distance
  
  
  if __name__ == "__main__":
      _input = sys.stdin.readlines()
      vertices, edges, root = map(int, _input[0].split())
      v_info = map(lambda x: x.split(), _input[1:])
      # assert len(init_vertices_table) == vertices_num
  
      distance = [float("inf")] * vertices
      parents = [-1] * vertices
      color = [WHITE] * vertices
      init_adj_table = tuple(dict() for _ in range(vertices))
  
      adj_table = generate_adj_table(v_info)
      ans = dijkstra_path_heap()
  
      # print('\n'.join(('INF' if isinf(ele) else str(ele) for ele in ans)))
      for ele in ans:
          if isinf(ele):
              print("INF")
          else:
              print(ele)
  
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"}]