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

using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");

int const nmax = 18;
int const statemax = (1<<nmax);
int const inf = 20000000;

int n, m, sol;
int dp[statemax][nmax];
vector<int> gr[nmax];
int cost[nmax][nmax];

int main() {
  in>>n>>m;
  for(int i = 0 ; i < m ;i++) {
    int c, a, b;
    in >> a >> b >> c;
    gr[a].push_back(b);
    cost[a][b] = c;
  }

  int finalstate = (1<<n) - 1;
  for(int i = 0 ; i < n ;i++) {
    for(int j = 1 ; j <= finalstate;j++) {
      dp[j][i] = inf;
    }
  }
  dp[1][0] = 0;

  //Tema optionala (foarte interesanta) dupa ce termini celelate dinamici
  //Sa implementezi solutie cu DFS (75 de puncte, restul TLE)
  //Sa implementezi solutie cu BFS (90 de puncte, restul TLE)
  //Sa te folosesti de matricea existenta (sa nu aloci memorie extra pentru coada si sa iei 100

  for(int i = 1 ; i <= finalstate ;i++) {
    for(int j = 0 ; j < n ;j++) {
      if( (i & (1<<j)) != 0 ) {
        for(int h = 0 ;h < gr[j].size() ; h++){
          int node = gr[j][h];
          int stare = (i | (1<<node));
          if(stare != i) {
            dp[stare][node] = min(dp[stare][node] , dp[i][j] + cost[j][node]);
          }
        }
      }
    }
  }

  int sol = inf;
  for(int i = 1 ; i < n; i++){
    if(0 < cost[i][0])
      sol = min(sol, dp[finalstate][i] + cost[i][0]);
  }
  if(sol < inf)
    out<<sol;
  else
    out<<"Nu exista solutie";

  return 0;
}