output_description: If 9 is contained in the decimal notation of N, print `Yes`; if not, print
  `No`.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: from collections import Counter
  
  
  def read_line(*types):
      return [f(a) for a, f in zip(input().split(), types)]
  
  
  n, m, r = read_line(int, int, int)
  
  rs = [int(r) for r in input().split()]
  
  cities = Counter()
  
  routes = {}
  costs = {}
  for _ in range(m):
      a, b, c = read_line(int, int, int)
  
      cities[a] = 1
      cities[b] = 1
  
      if a in routes:
          routes[a][b] = c
      else:
          routes[a] = {b: c}
  
      if b in routes:
          routes[b][a] = c
      else:
          routes[b] = {a: c}
  
  for a in cities.keys():
      for b in cities.keys():
          if a not in costs:
              costs[a] = {}
          if b not in costs[a]:
              if a in routes and b in routes[a]:
                  costs[a][b] = routes[a][b]
              else:
                  costs[a][b] = 100000 + 1
  
  # print('*')
  
  keys = list(cities.keys())
  
  for k in keys:
      for i in keys:
          for j in keys:
              c = costs[a][k] + costs[k][b]
              if a != b and costs[a][b] > c:
                  costs[a][b] = c
  
  # print('*')
  
  
  def cost(selected):
      c = 0
      for i in range(len(selected) - 1):
          a = selected[i]
          b = selected[i + 1]
          c += costs[a][b]
      return c
  
  
  smallest = 100000 + 1
  
  
  def f(selected, rest):
      global smallest
      if len(rest) == 0:
          c = cost(selected)
          if smallest > c:
              smallest = c
      else:
          for i in range(len(rest)):
              r = rest[i]
              rest_copy = rest[:]
              del rest_copy[i]
              if cost(selected + [r]) < smallest:
                  f(selected + [r], rest_copy)
  
  
  f([], keys)
  print(smallest)
  
problem_description: Statement
  
  It is September 9 in Japan now.
  
  You are given a two-digit integer N. Answer the question: Is 9 contained in
  the decimal notation of N?
samples: [{"input": "29", "output": "Yes\n    \n\nThe one's digit of 29 is 9.\n\n* * *"}, {"input": "72", "output": "No\n    \n\n72 does not contain 9.\n\n* * *"}, {"input": "91", "output": "Yes"}]