#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 statemax = 262144;
int const inf = 20000000;


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

int main() {
//  cout << sizeof(dp) / 1024 << " kbytes" << endl;
  in >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y, c;
    in >> x >> y >> c;
    //cout << x << " " << y << " " << c << endl;
    gr[x].push_back(y);
    cost[x][y] = c;
  }

  int fullstate = (1 << n) - 1;
  for (int i = 1; i <= fullstate; i++)
    for (int j = 0; j < n; j++)
      dp[i][j] = inf;
  dp[1][0] = 0;

  for (int i = 1; i <= fullstate; i++)
    for (int j = 0; j < n; j++)
      if (((1 << j) & i) != 0) {
        for (int k = 0; k < gr[j].size(); k++) {
          int next = gr[j][k];
          int bits = (1 << next);
          if ((bits & i) == 0)
            dp[i | bits][next] = std::min(dp[i | bits][next], dp[i][j] + cost[j][next]);
        }
      }

  sol = inf;
  for (int j = 1; j < n; j++)
    if (cost[j][0] > 0)
      sol = std::min(sol, cost[j][0] + dp[fullstate][j]);

  if (sol < inf)
    out << sol;
  else
    out << "Nu exista solutie";
  return 0;
}