#include <fstream>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

int const nmax = 18;
int const edgemax = nmax * nmax;
int const statemax = 262144;

struct State {
    int state;
    int node;
};
queue<State> q;

int n, m, sol, fullstate;
vector<int> gr[1 + nmax];
int cost[1 + nmax][1 + nmax];
int dp[statemax][1 + nmax];

int dfs(int state, int node) {
  if (state == fullstate) {
    if (0 < cost[node][0])
      if (sol == 0 || sol > dp[state][node] + cost[node][0])
        sol = dp[state][node] + cost[node][0];
  } else {
    for (int i = 0; i < gr[node].size(); i++) {
      int newnode = gr[node][i];
      if (((1 << newnode) & state) == 0) {
        int newstate = ((1 << newnode) | state);
        if (dp[newstate][newnode] == 0 || dp[newstate][newnode] > dp[state][node] + cost[node][newnode]) {
          dp[newstate][newnode] = dp[state][node] + cost[node][newnode];
          dfs(newstate, newnode);
        }
      }
    }
  }
}

int main() {
//  cout << sizeof(dp) / 1024 << " kbytes" << endl;
  in >> n >> m;
  fullstate = (1 << n) - 1;
  for (int i = 1; i <= m; i++) {
    int x, y, c;
    in >> x >> y >> c;
    gr[x].push_back(y);
    cost[x][y] = c;
  }
  dfs(1, 0);
  /*
  q.push({1, 0});
  while (0 < q.size()) {
    int state = q.front().state;
    int node = q.front().node;
    q.pop();
//    cout << node << endl;

    if (state == fullstate) {
      if (0 < cost[node][0])
        if (sol == 0 || sol > dp[state][node] + cost[node][0])
          sol = dp[state][node] + cost[node][0];
    } else {
      for (int i = 0; i < gr[node].size(); i++) {
        int newnode = gr[node][i];
        if (((1 << newnode) & state) == 0) {
          int newstate = ((1 << newnode) | state);
          if (dp[newstate][newnode] == 0 || dp[newstate][newnode] > dp[state][node] + cost[node][newnode]) {
            dp[newstate][newnode] = dp[state][node] + cost[node][newnode];
            q.push({newstate, newnode});
          }
        }
      }
    }
  }
*/
  if (0 < sol)
    out << sol;
  else
    out << "Nu exista solutie";
  return 0;
}