output_description: Print "4", "3", "2", "1" or "0" in a line.
input_description: Coordinates and radii of $c1$ and $c2$ are given in the following format.
  
  $c1x \; c1y \; c1r$  
  $c2x \; c2y \; c2r$
  
  $c1x$, $c1y$ and $c1r$ represent the center coordinate and radius of the first
  circle. $c2x$, $c2y$ and $c2r$ represent the center coordinate and radius of
  the second circle. All input values are given in integers.
attempt: # Single Source Shortest Path
  class node:
      def __init__(self, v, cost):
          self.v = v
          self.cost = cost
  
  
  infty = 999999999
  dict_c = {}
  [vertex, edge, r] = list(map(int, input("").split()))
  root_c = [node(r, 0)]
  final_c = [infty for i in range(vertex)]
  final_c[r] = 0
  
  for i in range(edge):
      [e1, e2, c] = list(map(int, input("").split()))
      if e1 == r:
          root_c.append(node(e2, c))
          final_c[e2] = c
      else:
          dict_c[(e1, e2)] = c
  
  
  def min_heap(i):
      global root_c
      l = 2 * i
      r = 2 * i + 1
      if l <= len(root_c) - 1 and root_c[l].cost <= root_c[i].cost:
          if root_c[l].cost < root_c[i].cost:
              min = l
          elif root_c[l].v < root_c[i].v:
              min = l
          else:
              min = i
      else:
          min = i
      if r <= len(root_c) - 1 and root_c[r].cost <= root_c[min].cost:
          if root_c[r].cost < root_c[min].cost:
              min = r
          elif root_c[r].v < root_c[min].v:
              min = r
          # else:
  
      if min != i:
          root_c[i], root_c[min] = root_c[min], root_c[i]
          min_heap(min)
  
  
  def build_min_heap():
      global root_c
      length = len(root_c) - 1
      for i in range(int(length / 2), 0, -1):
          min_heap(i)
  
  
  def extract_min():
      global root_c
      min = root_c[1]
  
      # print("min_cost  ", root_c[1].cost, root_c[2].cost, root_c[3].cost, root_c[4].cost, root_c[5].cost, root_c[6].cost, root_c[7].cost)
      # print("min_vertex", root_c[1].v, root_c[2].v, root_c[3].v, root_c[4].v, root_c[5].v, root_c[6].v, root_c[7].v)
  
      root_c[1] = root_c[len(root_c) - 1]
  
      # print("1: ",root_c[1].cost, root_c[1].v)
  
      del root_c[len(root_c) - 1]
      min_heap(1)
  
      # print("min_cost  2", root_c[1].cost, root_c[2].cost, root_c[3].cost, root_c[4].cost, root_c[5].cost, root_c[6].cost)
      # print("min_vertex2", root_c[1].v, root_c[2].v, root_c[3].v, root_c[4].v, root_c[5].v, root_c[6].v)
      # print("length: ",len(root_c))
  
      return min
  
  
  def decrease_key(i, c):
      global root_c
      root_c[i].cost = c
      while i > 1 and root_c[int(i / 2)].cost >= root_c[i].cost:
          if root_c[int(i / 2)].cost > root_c[i].cost:
              root_c[int(i / 2)], root_c[i] = root_c[i], root_c[int(i / 2)]
          elif root_c[int(i / 2)].v > root_c[i].v:
              root_c[int(i / 2)], root_c[i] = root_c[i], root_c[int(i / 2)]
          else:
              root_c[int(i / 2)], root_c[i] = root_c[int(i / 2)], root_c[i]
          i = int(i / 2)
  
  
  def min_insert(v, c):
      global infty, root_c
      for i in range(1, len(root_c)):
          if root_c[i].v == v:
              decrease_key(i, c)
              return
  
      root_c.append(node(v, infty))
      decrease_key(len(root_c) - 1, c)
  
  
  def Dijkstra(root, n):
  
      count = 1
  
      global infty, dict_c, root_c, final_c
      label = [i for i in range(n)]
  
      # print(count, label[root], final_c[label[root]])
      count += 1
  
      del label[root]
  
      while len(label) != 0:
          if len(root_c) > 1:
              min_node = extract_min()
          else:
              break
  
          for i in range(len(label)):
              if min_node.v == label[i]:
                  delete_label = i
                  continue
  
              if ((min_node.v, label[i]) in dict_c.keys()) == True:
                  if (
                      final_c[label[i]]
                      > final_c[min_node.v] + dict_c[(min_node.v, label[i])]
                  ):
                      final_c[label[i]] = (
                          final_c[min_node.v] + dict_c[(min_node.v, label[i])]
                      )
                      min_insert(label[i], final_c[label[i]])
  
          # print(count, label[delete_label], final_c[label[delete_label]])
          count += 1
  
          del label[delete_label]
  
  
  build_min_heap()
  
  """
  print("root_c :")
  for i in range(len(root_c)):
      print(root_c[i].cost)
  print("\n")
  """
  
  Dijkstra(r, vertex)
  
  # print("\n")
  
  for i in range(vertex):
      if final_c[i] == infty:
          print("INF")
      else:
          print(final_c[i])
  
problem_description: Intersection of Circles
  
  For given two circles $c1$ and $c2$, print
  
      
      
      4
      
  
  if they do not cross (there are 4 common tangent lines),
  
      
      
      3
      
  
  if they are circumscribed (there are 3 common tangent lines),
  
      
      
      2
      
  
  if they intersect (there are 2 common tangent lines),
  
      
      
      1
      
  
  if a circle is inscribed in another (there are 1 common tangent line),
  
      
      
      0
      
  
  if a circle includes another (there is no common tangent line).
samples: [{"input": "1 1 1\n    6 2 2", "output": "4"}, {"input": "1 2 1\n    4 2 2", "output": "3"}, {"input": "1 2 1\n    3 2 2", "output": "2"}, {"input": "0 0 1\n    1 0 2", "output": "1"}, {"input": "0 0 1\n    0 0 2", "output": "0"}]