#include<fstream>
#include<vector>

using namespace std;

#define NMAX 18
#define INF 1000000000

ifstream fi("hamilton.in");
ofstream fo("hamilton.out");

int n,m,x,y,i,j,k,rez=INF;
int cost[NMAX][NMAX],c[1<<NMAX][NMAX];

vector<int> v[NMAX];

int main() {
  // Citeste: n - numarul de noduri, m - numarul de muchii
  fi>>n>>m;

  // Initializeaza costurile cu infinit
  for(i=0;i<n;++i)
   for(j=0;j<n;++j) cost[i][j]=INF;

  // Citeste muchiile si costurile lor
  while(m--) {
    fi>>x>>y;
    fi>>cost[x][y];
    v[y].push_back(x);
  }

  // Initializeaza matricea c
  for(i=0;i<(1<<n);++i)
   for(j=0;j<n;++j) c[i][j]=INF;
  c[1][0]=0;

  // Calculeaza matricea c
  for(i=0;i<(1<<n);++i)
   for(j=0;j<n;++j)
    if(i&(1<<j)) // daca configuratia binara i contine nodul j
     for(k=0;k<v[j].size();++k)
      if(i&(1<<v[j][k])) // daca config. binara i contine vecinul k al lui j
       c[i][j]=min(c[i][j],c[i^(1<<j)][v[j][k]]+cost[v[j][k]][j]);

  // Calculeaza costul ciclului hamiltonian de cost minim daca exista
  for(i=1;i<n;i++)
   rez=min(rez,c[(1<<n)-1][i]+cost[i][0]);

  // Afiseaza rezultatul
  if(rez==INF) fo<<"Nu exista solutie\n";
  else fo<<rez<<"\n";
  return 0;
}