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

#define INF 0x3f3f3f3f

using namespace std;
vector<vector<int>> DP, Cost;
vector<vector<short>> Graph;
vector<bitset<1<<18>> Computed;

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

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

  Computed[to][mask] = true;
  return DP[to][mask];
}

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(N);
  Computed.resize(N);
  fill(DP.begin(), DP.end(), vector<int>(1<<N, INF));

  // assume we start the cycle in node 0;
  DP[0][1<<0] = 0; // we visited 0th node, and the cost is 0
  Computed[0][1<<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}
    best = min(best, dynamic(from, (1<<N)-1) + Cost[from][0]);
  }
  
  if (best != INF)
    fout << best << "\n";
  else
    fout << "Nu exista solutie\n";
  
  return 0;
}