#include <bits/stdc++.h>
#define L 20
#define LL (1 << 18) + 5
#define INVALID -1
#define INF 1000000001
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int cost[L][L], ham[LL][L];

int generate_ham(int n){
  for (int mask = 0; mask < (1 << n); mask++)
    for (int node = 0; node < n; node++)
      ham[mask][node] = INF;
  ham[1][0] = 0;
  for (int mask = 1; mask < (1 << n); mask++)
    for (int node = 0; node < n; node++){
//      if (ham[mask | (1 << node)][node] != INVALID)
//        continue;
//      ham[mask | (1 << node)][node] = INF;
      for (int i = 0; i < n; i++) {
        if ((mask & ( 1 << i)) == 0 || (bool)( mask & (1 << node) ) ) continue;
        ham[mask | (1 << node)][node] = min(ham[mask | (1 << node)][node], ham[mask][i] + cost[i][node]);
      }
//      if (ham[mask | (1 << node)][node] == INF)
//        ham[mask | (1 << node)][node] = INVALID;
    }
  int ans = INF;
  for (int node = 1; node < n; node++)
//    if (cost[node][0] != 0)
      ans = min(ans, ham[(1 << n) - 1][node] + cost[node][0]);
//  if (ans == INF)
//    ans = -1;
  return ans;
}

int main(){
  int n, m;
  fin >> n >> m;
  for ( int i = 0; i < n; i ++ ) {
    for ( int j = 0; j < n; j ++ ) {
      cost[i][j] = INF;
    }
  }
  for (int i = 1; i <= m; i++){
    int a, b, c;
    fin >> a >> b >> c;
    cost[a][b] = c;
  }
  int ans = generate_ham(n);
  if (ans == INF)
    fout << "Nu exista solutie\n";
  else
    fout << ans << "\n";
  return 0;
}