#include <fstream>
#include <vector>
 
using namespace std;
 
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
 
const int MAX_MASK = (1 << 18);
const int INF = 1e9;
 
void solve(int n, vector < vector < int > > &dp, 
  vector < vector < pair < int, int > > > &gr, int &sol) {
 
  dp[0][1] = 0;
  int val_max_mask = (1 << n) - 1;
  for (int mask = 1; mask <= val_max_mask; mask ++) {
    for (int nod = 0; nod < n; nod ++) {
      if (dp[nod][mask] == INF) {
        continue;
      }
 
      for (auto x : gr[nod]) {
        if (mask == val_max_mask) {
          if (x.second == 0) {
            int cost = x.first;
            sol = min(sol, dp[nod][mask] + cost);
            break;
          }
        }
 
        int next_node = x.second;
        int bit = (1 << next_node);
        if ((mask & bit) != 0) {
          continue;
        }
 
        int cost = x.first;
        dp[next_node][mask ^ bit] = min(dp[next_node][mask ^ bit], dp[nod][mask] + cost);
      }
    }
  }
 
  if (sol != INF) {
    cout << sol << '\n';
  }
  else {
    cout << "Nu exista solutie\n";
  }
}
 
int main(int argc, char const *argv[]) {
   
  int n, m;
  cin >> n >> m;
 
  vector < vector < pair < int, int > > > gr(n + 1);
 
  for (int i = 1; i <= m; i ++) {
    int x, y, cost;
    cin >> x >> y >> cost;
 
    gr[x].push_back({cost, y});
  }
 
  int sol = INF;
  vector < vector < int > > dp(n + 1, vector < int > (MAX_MASK, INF));
  solve (n, dp, gr, sol);
}