#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define NMAX 18
#define INF 0x3f3f3f3f
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)<(b)?(a):(b))

using namespace std;

ifstream in ( "hamilton.in" );
ofstream out ( "hamilton.out" );

int StartCost[NMAX][NMAX] , Answer;
int N , M , Cost[(1<<NMAX) + 2][NMAX];
vector < int > G[NMAX];


int main ( void ){
   int i , j  , x, y;
      in >> N >> M ;
      for ( i = 1 ; i <= N ; ++i ){
        in >> x >> y >> Cost[x][y];
        G[x].push_back(y);
      }

   memset ( Cost , INF , sizeof(Cost));
   for ( i = 1 ; i <= ( 1<< N ) ; ++i )
     for ( j = 1 ; j <= N ; ++j )
          if ( i & (1<<j) )
        for ( vector < int > ::iterator it = G[j].begin() ; it != G[j].end() ; ++it )
          if ( i & ( 1<<(*it)))
       Cost[i][j] = get_min(Cost[i][j] , StartCost[*it][i] + Cost[i^(1<<j)][*it]);
    Answer = INF ;
   for ( vector < int > ::iterator it = G[0].begin () ; it != G[0].end() ; ++it )
   Answer = get_min( Answer , StartCost[*it][0] + Cost[(1<<N)^(1<<0)][*it] );
   out << Answer << "\n";
   return 0 ;
}