#include <fstream>
#include <vector>

using namespace std;

const int N = 18;
const int INF = (1 << 29);

int dp[N][1 << N], cost[N][N];

int main() {
  ifstream cin("hamilton.in");
  ofstream cout("hamilton.out");
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      cost[i][j] = INF;
  while (m--) {
    int x, y;
    cin >> x >> y;
    cin >> cost[x][y];
  }
  cin.close();
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < (1 << n); ++j)
      dp[i][j] = INF;
  dp[0][1] = 0;
  for (int j = 0; j < (1 << n) - 1; ++j)
    for (int i = 0; i < n; ++i) {
      if (!(j & (1 << i)))
        continue;
      for (int to = 0; to < n; ++to) {
        if (j & (1 << to))
          continue;
        dp[to][j | (1 << to)] = min(dp[to][j | (1 << to)], dp[i][j] + cost[i][to]);
      }
    }
  int ans = INF;
  for (int i = 1; i < n; ++i)
    ans = min(ans, dp[i][(1 << n) - 1] + cost[i][0]);
  if (ans != INF)
    cout << ans << "\n";
  else
    cout << "Nu exista solutie\n";
  cout.close();
  return 0;
}