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: class RadixHeap:
      __slots__ = ["data", "last", "siz", "used"]
  
      # (max_key - min_key) <= C
      def __init__(self, N, C):
          self.data = [[] for i in range(C.bit_length() + 1)]
          self.last = self.siz = 0
          self.used = [0] * N
  
      def push(self, x, key):
          # assert self.last <= x
          self.siz += 1
          self.data[(x ^ self.last).bit_length()].append((x, key))
  
      def pop(self):
          data = self.data
          used = self.used
          # assert self.siz > 0
          if not data[0]:
              i = 1
              while not data[i]:
                  i += 1
              d = data[i]
              new_last, new_key = min(d)
              used[new_key] = 1
              for val in d:
                  x, key = val
                  if used[key]:
                      self.siz -= 1
                      continue
                  data[(x ^ new_last).bit_length()].append(val)
              self.last = new_last
              data[i] = []
          else:
              new_last, new_key = data[0].pop()
              used[new_key] = 1
              self.siz -= 1
          return new_last, new_key
  
      def __len__(self):
          return self.siz
  
  
  import sys
  
  readline = sys.stdin.readline
  write = sys.stdout.write
  
  N, M, s = map(int, readline().split())
  G = [[] for i in range(N)]
  for i in range(M):
      a, b, c = map(int, readline().split())
      G[a].append((b, c))
  
  INF = 10**18
  
  
  def dijkstra(N, G, s):
      que = RadixHeap(N, 10**9 + 1)
  
      dist = [INF] * N
      dist[s] = 0
      que.push(0, s)
      while que:
          cost, v = que.pop()
          if dist[v] < cost:
              continue
          for w, c in G[v]:
              if cost + c < dist[w]:
                  dist[w] = r = cost + c
                  que.push(r, w)
      return dist
  
  
  dist = dijkstra(N, G, s)
  for c in dist:
      write("INF\n" if c == INF else "%d\n" % c)
  
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"}]