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

#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 , a;
      in >> N >> M ;
      memset ( StartCost , INF , sizeof(StartCost));

      for ( i = 1 ; i <= M ; ++i ){
        in >> x >> y >> a;
        G[y].push_back(x);
        StartCost[x][y] = a;
      }

   memset ( Cost , INF , sizeof(Cost));
   Cost[1][0] = 0;
   for ( i = 0 ; i < ( 1<< N ) ; ++i )
     for ( j = 0 ; 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][j] + 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][*it] );
   out << Answer << "\n";
   return 0 ;
}