#include <stdio.h>

#define magic_sauce inline __attribute__((always_inline))

magic_sauce int min( int a, int b ){ return a < b ? a : b; }

const int MAXN = 18;
const int SUMB = (1 << MAXN);
const int INF = 1e9;

int cost[MAXN][MAXN];

int mincost[SUMB][MAXN];

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

  int n, m, i, a, b, p2, mask, pb;

  fscanf( fin, "%d%d", &n, &m );
  for( a = 0 ; a < n ; a++ )
    for( b = 0 ; b < n ; b++ )
      cost[a][b] = +INF;
  
  for( i = 0 ; i < m ; i++ ){
    fscanf( fin, "%d%d", &a, &b );
    fscanf( fin, "%d", &cost[a][b] );
  }

  p2 = (1 << n);
  for( mask = 0 ; mask < p2 ; mask++ )
    for( i = 0 ; i < n ; i++ )
      mincost[mask][i] = +INF;

  mincost[0][0] = 0;
  for( mask = 0 ; mask < p2 ; mask++ )
    for( a = 0 ; a < n ; a++ )
      for( b = 0 ; b < n ; b++ ){
        pb = (1 << b);
        if( !(mask & pb) )
          mincost[mask | pb][b] = min( mincost[mask | pb][b], mincost[mask][a] + cost[a][b] );
      }

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

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