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

using namespace std;

ifstream fin( "hamilton.in" );
ofstream fout( "hamilton.out" );

const int INF = (int)1e9;
const int MAXN = 19;

int main() {
  int n, m, u, v, c;

  fin >> n >> m;
  
  vector<vector<int>> cost(n, vector<int>(n, INF));
  vector<vector<int>> dp((1 << n), vector<int>(n, INF));
  
  while (m--) { 
	fin >> u >> v >> c;
    cost[u][v] = c;
  }
  dp[1][0] = 0;
  for ( int mask = 1; mask < (1 << n); ++mask ) {
	if ( (mask & 1) == 0 ) continue;
	for ( int lst = 0; lst < n; ++lst ) {
	  for ( int nxt = 0; nxt < n; ++nxt ) {
		if ( (mask & (1 << nxt)) == 0 && cost[lst][nxt] != INF ) {
		  dp[mask + (1 << nxt)][nxt] = min(dp[mask + (1 << nxt)][nxt], dp[mask][lst] + cost[lst][nxt]);
		}
	  }
	}
  }
  int res = INF;
  for ( int lst = 0; lst < n; ++lst ) {
	if ( cost[lst][0] != INF ) {
	  res = min(res, dp[(1 << n) - 1][lst] + cost[lst][0]);
	}
  }
  if ( res == INF ) {
	fout << "Nu exista solutie";
  } else {
    fout << res;
  }
  fin.close();
  fout.close();
  return 0;
} // ahh