INF=1<<30

def solveTest(inputfile, outputfile):

  # readInput, readsInput from TSP.in return (number of nodes, List of lists of edges (to, cost))
  def readInput(input):
    #input format is number of Nodes, number of Edges, then edges u v cost
    #aux function for reading an int
    N, M=[int(x) for x in input.readline().split()]
    edges = [[] for i in range(N)]
    for i in range(M):
      a,b,c=[int(x) for x in input.readline().split()]
      edges[a].append((b, c))
      #edges[b].append((a, c)) add this if your graph is unordered
    return (N, edges)

  input=open(inputfile, 'r')
  output=open(outputfile, 'w')
  N, edges=readInput(input)

  maxMask=(1<<N)

  dp=[[INF for i in range(N)] for i in range(maxMask)]
  dp[1][0]=0

  for mask in range(maxMask):
    for i in range(N):
      if dp[mask][i]==INF or not (1<<i)&mask: continue
      for to, cost in edges[i]:
        if (1<<to)&mask: continue
        dp[mask|(1<<to)][to]=min(dp[mask|(1<<to)][to], dp[mask][i]+cost)

  sol=INF
  for i in range(1, N):
    for to,cost in edges[i]:
      if to != 0: continue
      sol=min(sol, dp[maxMask-1][i]+cost)

  if sol==INF:
    print("Nu exista solutie", file=output)
  else:
    print(sol, file=output)


for i in range(21):
  solveTest(f"grader_test{i}.in", f"grader_test{i}.out")