#include <iostream>
#include <vector>
#define NMAX 18
#define B2MAX ( 1 << NMAX )
#define NUL 20000000

using namespace std;

int cost[NMAX][NMAX];
int dp[B2MAX][NMAX];
vector <int> graf[NMAX];

int main() {
    FILE *fin, *fout;
    int n, m, i, j, a, b, cnt, rez;
    fin = fopen( "hamilton.in", "r" );
    fout = fopen( "hamilton.out", "w" );
    fscanf( fin, "%d%d", &n, &m );
    for( i = 0; i < n; i++ )
      for( j = 0; j < n; j++ )
        cost[i][j] = NUL;
    for( i = 0; i < ( 1 << n ); i++ )
      for( j = 0; j < n; j++ )
        dp[i][j] = NUL;
    for( i = 0; i < m; i++ ) {
      fscanf( fin, "%d%d", &a, &b );
      graf[a].push_back(b);
      fscanf( fin, "%d", &cost[a][b] );
    }
    dp[1][0] = 0;
    for( i = 0; i < ( 1 << n ); i++ ) {
      for( j = 0; j < n; j++ ) {
        if( i & ( 1 << j ) ) {
          for( cnt = 0; cnt < graf[j].size(); cnt++ )
            dp[i][graf[j][cnt]] = min( dp[i^(1<<graf[j][cnt])][j] + cost[j][graf[j][cnt]], dp[i][graf[j][cnt]] );
        }
      }
    }
    rez = NUL;
    for( i = 0; i < n; i++ )
      if( rez > dp[(1<<n)-1][i] + cost[i][0] )
      rez = dp[(1<<n)-1][i] + cost[i][0];
    if( rez == NUL )
      fprintf( fout, "Nu exista solutie" );
    else
      fprintf( fout, "%d", rez );
    fclose( fin );
    fclose( fout );
    return 0;
}