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: #!python3
  
  iim = lambda: map(int, input().rstrip().split())
  
  from heapq import heappush, heappop
  
  
  def resolve():
      V, E = iim()
      inf = float("inf")
      ad = [[inf] * V for i in range(V)]
  
      for i in range(E):
          s, t, d = iim()
          ad[s][t] = d
  
      bi = [1 << i for i in range(V)]
      goal = (1 << V) - 1
  
      dp = dict()
      q = []
      heappush(q, (0, 0, 1))
      ans = inf
      while q:
          cost, v, state = heappop(q)
  
          vs = (v, state)
          if vs in dp:
              if dp[vs] <= cost:
                  continue
          dp[vs] = cost
  
          if state == goal:
              cost += ad[v][0]
              if cost < ans:
                  ans = cost
              continue
  
          for i in range(V):
              if bi[i] & state:
                  continue
              heappush(q, (cost + ad[v][i], i, state | bi[i]))
      print(ans if ans != inf else -1)
      # print(dp[(0, goal)])
  
  
  if __name__ == "__main__":
      resolve()
  
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"}]