#include <fstream>
#include <vector>
#include <bitset>

#define INF 0x3f3f3f3f

using namespace std;
vector<vector<int>> DP, Cost;
vector<vector<short>> Graph;

int dynamic(int mask, int to)
{
  if (DP[mask][to] < INF)
    return DP[mask][to];

  if (mask == 0)
    return INF;
  
  for (auto from: Graph[to])
    if (mask & (1<<from))
      DP[mask][to] = min(DP[mask][to], dynamic(mask ^ (1<<to), from) + Cost[from][to]); 

  return DP[mask][to];
}

int main()
{
  ifstream fin("hamilton.in");
  ofstream fout("hamilton.out");
  fin.sync_with_stdio(false);
  fin.tie(0);
  
  int N, M;
  fin >> N >> M;

  Graph.resize(N);
  Cost.resize(N);
  fill(Cost.begin(), Cost.end(), vector<int>(N, 0));

  for (int i = 0; i < M; ++i) {
    int from, to, cost;
    fin >> from >> to >> cost;
    Graph[to].emplace_back(from);
    Cost[from][to] = cost;    
  }
  
  DP.resize(1<<N);
  fill(DP.begin(), DP.end(), vector<int>(N, INF));

  // assume we start the cycle in node 0;
  DP[1<<0][0] = 0; // we visited 0th node, and the cost is 0
  
  int best = INF;
  for (auto from : Graph[0]) { // the closing edge
    // start in `0`, go through all nodes and finish in `from` and close with edge {from,0}
    best = min(best, dynamic((1<<N)-1, from) + Cost[from][0]);
  }

  if (best != INF)
    fout << best << "\n";
  else
    fout << "Nu exista solutie\n";
  
  return 0;
}