INF=1<<31
INPUTFILE="hamilton.in"
OUTPUTFILE="hamilton.out"

# 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)]
for i in range(N):
  dp[1<<i][i]=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)

print(sol, file=output)