#include <fstream>
#include <vector>
#include <iostream>
#include <limits>
 
#define INF 0x3f3f3f3f
 
using namespace std;
vector<vector<int>> DP, Cost, Graph;
 
int dynamic(int mask, int to)
{
  if (DP[mask][to] != -1)
    return DP[mask][to];

  if (mask == 1 && to == 0)
    return 0;
  
  if (mask == 0)
    return INF;
  
  for (auto from: Graph[to])
    if (mask & (1<<from)) 
      if (DP[mask][to] == -1)
	DP[mask][to] = dynamic(mask ^ (1<<to), from) + Cost[from][to];
      else
	DP[mask][to] = min(DP[mask][to], dynamic(mask ^ (1<<to), from) + Cost[from][to]);
  if (DP[mask][to] < 0)
    DP[mask][to] = INF;
  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, -1));
 
  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;
}