#include <bits/stdc++.h>
#define nmax 50005

using namespace std;

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

int cost[19][19];
int dp[1 << 19][19];
const int oo (1 << 30);
vector <int> vec[19];

int main()
{
  int n, m;
  f >> n >> m;
  while (m --)
  {
      int x, y ,c;
      f >> x >> y >> c;
      cost[x][y] = c;
      vec[x].push_back(y);
  }

  for (int mask = 1; mask < (1 << n); ++ mask)
        for (int last = 0; last < n; ++ last)
            dp[mask][last] = oo;

  dp[1][0] = 0;
  for (int mask = 1; mask < (1 << n); ++ mask)
      for (int last = 0; last < n; ++ last)
          if (mask & (1 << last))
              for (auto now : vec[last])
                  if (!(mask & (1 << now)))
                      dp[mask | (1 << now)][now] = min(dp[mask | (1 << now)][now], dp[mask][last] + cost[last][now]);

  int ans = oo;
  for (int last = 1; last < n; ++ last)
      if (cost[last][0])
          ans = min(ans, dp[(1 << n) - 1][last] + cost[last][0]);
  if (ans == oo)
      g << "Nu exista solutie";
  else
      g << ans;
}