#include <cstdio>
#include <memory>
#include <vector>
#include <bitset>

using namespace std;

class Solver{
private:
  const int INF = 0x3f3f3f3f;
  static const int Nmax = (1<<18);
  int N, M;
  vector<vector<int>> Graph, Cost;
  vector<vector<int>> DP;
  bitset<18> Computed[Nmax];
public:
  Solver() {
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
  }
  ~Solver() {
    fclose(stdin);
    fclose(stdout);
  }
  void ReadData() {
    scanf("%d%d", &N, &M);
    Graph.resize(N);
    Cost.resize(N, vector<int>(N));
    int from, to, cst;
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%d", &from, &to, &cst);
      Graph[to].emplace_back(from);
      Cost[from][to] = cst;
    }
  }
  
  int hamilton(int mask, int k) {
    if (!(mask & (1<<k))) // I went through the mask and finished in k but k is not flipped
      return INF;
    
    if (Computed[mask][k])
      return DP[mask][k];

    int best = INF;
    for (auto previous: Graph[k])
      if (mask & (1<<previous))
	best = min(best, hamilton(mask ^ (1<<k), previous) + Cost[previous][k]);
    DP[mask][k] = best;
    Computed[mask][k] = true;
    
    return DP[mask][k];
  }
  void Solve() {
    int mask = (1 << N) - 1;
    int best = INF;
    DP.resize((1<<N), vector<int>(N, INF));
    DP[1][0] = 0;
    Computed[1][0] = true;

    for (auto k: Graph[0]) // last node before coming to 0
      best = min(best, hamilton(mask, k) + Cost[k][0]);
    if (best >= INF)
      printf("Nu exista solutie\n");
    else
      printf("%d\n", best);
  }
};

int main()
{
  unique_ptr<Solver> s = make_unique<Solver>();
  s->ReadData();
   s->Solve();
  return 0;
}