#include <iostream>
#include <fstream>
#include <vector>
#define DEBUG 0
#define MAXN 18
#define MAXVAL 1000000000
#define DEBUG 0

using namespace std;

struct Edge{
  int a, cost;

  bool operator>(const Edge& other) const{
    return cost > other.cost;
  }
};
vector<vector<Edge>> v;

int costToStart[MAXN];

int d[MAXN][1 << (MAXN)];

int getD(int i, int g){
  if(g < 0)
    return MAXVAL;
  if((g ^ (1 << i)) > g) // G nu contine nodul i
    return MAXVAL;

  if(d[i][g] != MAXVAL)
    return d[i][g];
  if(g == (1 << i)) // Este un singur nod si nu este 0
    return MAXVAL;

  for(int j = 0; j < v[i].size(); j ++){
    Edge e = v[i][j];
    int val = getD(e.a, g - (1 << i)) + e.cost;
    if(val < d[i][g])
      d[i][g] = val;
  }
  return d[i][g];
}

int main(){
  int n, m;

  ifstream fin ("hamilton.in");
  fin >> n >> m;
  v.resize(n);

  for(int i = 0; i < n; i ++)
    costToStart[i] = MAXVAL;
  for(int i = 0; i < n; i ++){
    for(int j = 0; j < (1 << n); j ++)
      d[i][j] = MAXVAL;
  }
  d[0][1] = 0;

  for(int i = 0; i < m; i ++){
    int a, b, c;
    fin >> a >> b >> c;
    v[b].push_back({a, c}); // toate muchiile care ajung in b
    if(b == 0)
      costToStart[a] = c;
  }
  fin.close();

  int minv = MAXVAL;
  for(int i = 1; i < n; i ++){
    int val = getD(i, (1 << n) - 1) + costToStart[i];
    if(val < minv)
      minv = val;
  }
  
  if(DEBUG){
    printf("   ");
    for(int i = 0; i < (1 << n); i ++){
      printf("%d ", i);
      if(i < 10)
        printf(" ");
    }
    printf("\n");
    for(int i = 0; i < n; i ++){
      printf("%d: ", i);
      for(int j = 0; j < (1 << n); j ++){
        if(getD(i, j) == MAXVAL)
          printf("-  ");
        else {
          printf("%d ", getD(i, j));
          if(getD(i,j) < 10)
            printf(" ");
        }
      }
      printf("\n");
    }
  }

  ofstream fout ("hamilton.out");
  if(minv >= MAXVAL)
    fout << "Nu exista solutie" << endl;
  else
    fout << minv << "\n";
  fout.close();

  return 0;
}