#include <stdio.h>
#include <algorithm>

#define NMAX 19 
#define INFINIT 1000000000

int g [ NMAX + 1 ] [ NMAX + 1 ] ; 
int d [ 1 << (NMAX + 1 ) ] [ NMAX + 1 ] ; 

int hamilton (int conf, int last, int n ) {
  int i ;
  if (d[conf][last] == -1 ) {
    d[conf][last] = INFINIT ; 
    for (i = 0 ; i < n ; i++ ) {
      if (g[last][i] > 0) {
        if (conf & (1 << i) == 1 ) {
          if (!(i == 0 && (conf == (1 << last) + 1)))
              d[conf][last] = std::min (d[conf][last], hamilton(conf ^ (1 << last), i, n) + g[i][last] ) ;   
        } 
      }
    }
  }
  return d[conf][last] ; 
}

int main () {
  
  FILE *fin, *fout ; 
  fin = fopen ("hamilton.in", "r" ) ; 
  fout = fopen ("hamilton.out", "w" ) ; 
  int x, y, c, n, m, i, j, sol ; 
  fscanf (fin, "%d%d", &n, &m ) ; 
  for (i = 1 ; i <= m ; i++ ) {
    fscanf (fin, "%d%d%d", &x, &y, &c) ;  
    g[y][x] = c ; 
  }
  for (i = 0 ; i < n ; i++ ) 
    d[1 << i][i] = -1 ;
  sol = INFINIT ; 
  d[1][0] = 0 ; 
  for (i = 0 ; i < n ; i++ ) {
    if (g[0][i] > 0 ) {
      sol = std::min (sol, hamilton((1 << n) - 1, i, n) + g[i][0] ) ; 
    }
  }
  if (sol == INFINIT) 
    fprintf (fout, "Nu exista solutie\n") ; 
  else 
    fprintf (fout, "%d", sol) ; 
  return 0 ; 
}