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 itertools import permutations
  
  N, M, R = [int(i) for i in input().split()]
  r = [int(i) - 1 for i in input().split()]
  V = N
  # Define infinity as the large enough value. This value will be
  # used for vertices not connected to each other
  INF = 10000000
  
  graph = [[INF for i in range(N)] for j in range(N)]
  
  for m in range(M):
      A, B, C = [int(i) for i in input().split()]
      A = A - 1
      B = B - 1
      graph[A][B] = C
      graph[B][A] = C
  
  
  # Solves all pair shortest path via Floyd Warshall Algrorithm
  def floydWarshall(graph):
      dist = graph
      for k in range(V):
  
          # pick all vertices as source one by one
          for i in range(V):
  
              # Pick all vertices as destination for the
              # above picked source
              for j in range(V):
  
                  # If vertex k is on the shortest path from
                  # i to j, then update the value of dist[i][j]
                  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
      return dist
  
  
  new_graph = floydWarshall(graph)
  smallest_dist = INF
  for sub_permute in permutations(r):
      tmp = 0
      for i in range(R - 1):
          tmp += new_graph[sub_permute[i]][sub_permute[i + 1]]
      smallest_dist = min(smallest_dist, tmp)
  print(smallest_dist)
  
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"}]