#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 18

using namespace std;

vector<vector<int>> v, cost;
int d[MAXN][2 << MAXN];

int noNodes, n, firstNode;

int getCost(int j, int mask, int s){
 // printf("%d ", j);
 // int mk = mask;
 // for(int i = n - 1; i >= 0; i --){
 //   if(mk >= 1 << i){
 //     printf("1");
 //     mk -= 1<<i;
 //   }
 //   else
 //     printf("0");
 // }
 // printf("  %d %d\n", noNodes + 1, n);

  if(d[j][mask] != 0){
    // if(noNodes == n - 1 && d[j][mask] != -1)
      // printf("----- ok ------\n");
    return d[j][mask];
  }

  noNodes ++; /// Mai folosim inca un nod

  int k, x, min = -1;
  for(k = 0; k < (int)v[j].size(); k ++){
    /// Daca toate nodurile sunt folosite si ajungem la primul
    if(noNodes == n && v[j][k] == firstNode){
      // printf("----- ok ------\n");
      noNodes --;
      d[j][mask] = s + cost[j][k];
      return s + cost[j][k];
    }

    if(!(mask & (1 << v[j][k]))){ /// Daca nu am mai folosit nodul o data
      x = getCost(v[j][k], mask | (1 << v[j][k]), s + cost[j][k]); /// Vedem cat ar costa ciclul din acel punct
      if(min == -1 || (x < min &&  x != -1))
        min = x;
    }
  }

  noNodes --;
  d[j][mask] = min;
  return min;
}

int main(){
  int i, a, b, c, m;

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

  for(i = 0; i < m; i ++){
    fin >> a >> b >> c;

    v[a].push_back(b);
    cost[a].push_back(c);
  }
  fin.close();

  noNodes = 0;
  firstNode = 0;

  ofstream fout("hamilton.out");
  // printf("%d\n", firstNode);

  int x = getCost(0, 1 << firstNode, 0);
  if(x == -1)
    fout << "Nu exista solutie" << endl;
  else
    fout << x << endl;
  fout.close();
  return 0;
}