#include <stdio.h>

#include <vector>
#include <algorithm>

constexpr int INF = 1e9;

int main() {
  FILE *fin = fopen( "hamilton.in", "r" );
  FILE *fout = fopen( "hamilton.out", "w" );

  int n, m;
  fscanf( fin, "%d%d", &n, &m );

  std::vector<std::vector<int>> adj(n, std::vector<int>(n, +INF));
  for( int i = 0; i < m; i++ ){
    int a, b, cost;
    fscanf( fin, "%d%d%d", &a, &b, &cost );
    adj[a][b] = std::min( adj[a][b], cost );
    // adj[b][a] = std::min( adj[b][a], cost );
  }

  int p2 = (1 << n);
  std::vector<std::vector<int>> dp(p2, std::vector<int>(n, +INF));
  for( int i = 0; i < n; i++ )
    dp[1 << i][i] = adj[0][i];

  for( int mask = 0; mask < p2; mask++ )
    for( int last = 0; last < n; last++ )
      if( (mask & (1 << last)) )
        for( int next = 0; next < n; next++ )
          if( !(mask & (1 << next)) ){
            int mask2 = mask | (1 << next);
            dp[mask2][next] = std::min( dp[mask2][next], dp[mask][last] + adj[last][next] );
          }

  fprintf( fout, "%d\n", dp[p2 - 1][0] );

  fclose( fin );
  fclose( fout );
  return 0;
}