#include <fstream>
#include <vector>

using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

const int MAX_MASK = (1 << 18)  - 1;
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 = 0; 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);
}