#include <iostream>

#define MAX_MASK 1000000
#define MAXN 19
#define INF 1000000000000
using namespace std;

long long cost[MAXN][MAXN];
long long bestWay[MAX_MASK][MAXN];

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

  int n, m, a, b, i, i2, i3;
  long long c, ans;

  fscanf(fin, "%d%d", &n, &m);

  for ( i = 0; i < n; i++ ) {
    for ( i2 = 0; i2 < n; i2++ ) {
      cost[i][i2] = INF;
    }
  }

  for ( i = 0; i < MAX_MASK; i++ ) {
    for ( i2 = 0; i2 < n; i2++ ) {
      bestWay[i][i2] = INF;
    }
  }

  for ( i = 0; i < m; i++ ) {
    fscanf(fin, "%d%d%lld", &a, &b, &c);

    cost[a][b] = c;
  }

  bestWay[1][0] = 0;

  for ( i = 0; i < (1 << n); i++ ) {
    for ( i2 = 0; i2 < n; i2++ ) {
      if ( i & (1 << i2) ) {
        for ( i3 = 0; i3 < n; i3++ ) {
          if ( !(i & (1 << i3)) ) {
            bestWay[i + (1 << i3)][i3] = min(bestWay[i + (1 << i3)][i3], bestWay[i][i2] + cost[i2][i3]);
          }
        }
      }
    }
  }

  ans = INF;

  for ( i = 0; i < n; i++ ) {
    ans = min(ans, bestWay[(1 << n) - 1][i] + cost[i][0]);
  }

  if ( ans == INF ) {
    fprintf(fout, "Nu exista solutie\n");
  } else {
    fprintf(fout, "%lld\n", ans);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}