#include <fstream>
#include <vector>
#include <bitset>
#include <memory.h> 
#define INF 0x3f3f3f3f
 
using namespace std;
vector<vector<pair<int,int>>> Graph;
bitset<18> Computed[1<<18];
int DP[1<<18][18];

int dynamic(int mask, int to)
{
  if (Computed[mask][to])
    return DP[mask][to];
 
  if (mask == 0)
    return INF;
  
  for (auto it: Graph[to]) {
    if (mask & (1<<it.first))
      if(DP[mask][to] > dynamic(mask ^ (1<<to), it.first) + it.second)
	DP[mask][to] = dynamic(mask ^ (1<<to), it.first) + it.second; 
  } 
  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);
 
  for (int i = 0; i < M; ++i) {
    int from, to, cost;
    fin >> from >> to >> cost;
    Graph[to].emplace_back(from, cost);
  }
  
  memset(DP, INF, sizeof(DP));
  // 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 it : 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, it.first) + it.second)
      best = dynamic((1<<N)-1, it.first) + it.second;
  }
 
  if (best != INF)
    fout << best << "\n";
  else
    fout << "Nu exista solutie\n";
  
  return 0;
}