#include <fstream>
#include <vector>
#include <bitset>
 
#define INF 0x3f3f3f3f
 
using namespace std;
vector<vector<int>> DP, Cost, Graph;
vector<bitset<18>> Computed;
 
int dynamic(int mask, int to)
{
  if (Computed[mask][to])
    return DP[mask][to];
 
  if (mask == 0)
    return INF;
  
  for (auto from: Graph[to])
    if (mask & (1<<from))
      if(DP[mask][to] > dynamic(mask ^ (1<<to), from) + Cost[from][to])
	DP[mask][to] = dynamic(mask ^ (1<<to), from) + Cost[from][to]; 
 
  Computed[mask][to] = true;
  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);
  Computed.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
  Computed[1<<0][0] = true;
  
  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}
    if (best > dynamic((1<<N)-1, from) + Cost[from][0])
      best = dynamic((1<<N)-1, from) + Cost[from][0];
  }
 
  if (best != INF)
    fout << best << "\n";
  else
    fout << "Nu exista solutie\n";
  
  return 0;
}