#include <cstring>
#include <fstream>
#include <vector>

using namespace std;

const int N_MAX = 18;
const int INF = 0x3f3f3f3f;

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

int N, M;
vector<pair<int, int>> GT[N_MAX];

int best[1 << N_MAX][N_MAX];
int ans = INF;

int main() {
   fin >> N >> M;
   while (M--) {
      int x, y, c;
      fin >> x >> y >> c;
      GT[y].emplace_back(x, c);
   }

   memset(best, INF, sizeof best);
   best[1][0] = 0;

   for (int conf = 3; conf < (1 << N); ++conf)
      for (int last = 0; last < N; ++last)
         if (conf & (1 << last)) {
            int prv = conf ^ (1 << last);
            for (const auto& it : GT[last])
               if (prv & (1 << it.first))
                  best[conf][last] = min(best[conf][last], best[prv][it.first] + it.second);
         }

   for (const auto& it : GT[0])
      ans = min(ans, best[(1 << N) - 1][it.first] + it.second);

   if (ans == INF)
      fout << "Nu exista solutie\n";
   else
      fout << ans << "\n";

   return 0;
}