output_description: Print the shortest distance in a line. If there is no solution, print -1.
input_description: |V| |E|
      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 the graph. The
  graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.
  
  si and ti represent source and target vertices of i-th edge (directed) and di
  represents the distance between si and ti (the i-th edge).
attempt: def tsp(matrix):
      INF = float("inf")
      n = len(matrix)
  
      # dp[bit_state][i] := すでにbit_stateの状態を訪れていて、
      #                     最後に訪問したのがi番目のときの最小値
      dp = [[INF] * n for i in range(1 << n)]
      dp[1 << 0][0] = 0
  
      for bit_state in range(1 << n):
          for i in range(n):
              # bit_stateにiを含んでいる
              if (bit_state >> i) & 1:
                  for j in range(n):
                      # bit_stateにjを含んでいない
                      if not ((bit_state >> j) & 1):
                          dp[bit_state | (1 << j)][j] = min(
                              dp[bit_state | (1 << j)][j], dp[bit_state][i] + matrix[i][j]
                          )
      ans = INF
      for i in range(n):
          ans = min(dp[(1 << n) - 1][i] + matrix[i][0], ans)
      return ans
  
  
  n, m = map(int, input().split())
  info = [list(map(int, input().split())) for i in range(m)]
  INF = float("inf")
  
  matrix = [[INF] * n for i in range(n)]
  for i in range(m):
      a, b, cost = info[i]
      matrix[a][b] = cost
  for i in range(n):
      matrix[i][i] = 0
  
  ans = tsp(matrix)
  if ans == INF:
      print(-1)
  else:
      print(ans)
  
problem_description: Traveling Salesman Problem
  
    
  
  For a given weighted directed graph G(V, E), find the distance of the shortest
  route that meets the following criteria:
  
    * It is a closed cycle where it ends at the same point it starts.
    * It visits each vertex exactly once.
samples: [{"input": "4 6\n    0 1 2\n    1 2 3\n    1 3 9\n    2 0 1\n    2 3 6\n    3 2 4", "output": "16"}, {"input": "3 3\n    0 1 1\n    1 2 1\n    0 2 1", "output": "-1"}]