#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
using namespace std;
typedef long long LL;

#ifdef INFOARENA
#define ProblemName "hamilton"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

#define MUTATION_PERCENT 70
#define MAX_GENERATIONS 100

const int MAXN = 19;
int N;
int M[MAXN][MAXN];
const int MAXCOST = 1000000;


class permutation : public vector<int> {
private:
  int fitness;
public:
  static vector<char> *aux0;
  static permutation *aux; //helps with faster cross
  void calculateFitness();
  int getFitness();
  permutation();
  permutation(int);
  permutation(const permutation&);
  void mutate();
  void cross(permutation&);
  bool operator<(const permutation&) const;
  permutation& operator=(const permutation&);
};

vector<char>* permutation::aux0 = NULL;
permutation* permutation::aux = NULL;

permutation::permutation(const permutation& b) {
  this->resize(b.size());
  for (unsigned int i = 0; i < b.size(); i++)
    (*this)[i] = b[i];
  this->fitness = b.fitness;
}

permutation& permutation::operator=(const permutation& b) {
  this->resize(b.size());
  for (unsigned int i = 0; i < b.size(); i++)
    (*this)[i] = b[i];
  this->fitness = b.fitness;
  return *this;
}

void permutation::mutate() {
  if (rand() % 100 < MUTATION_PERCENT) {
    unsigned int i1 = rand() % this->size(), i2 = rand() % this->size();
    int aux = (*this)[i1];
    (*this)[i1] = (*this)[i2];
    (*this)[i2] = aux;
  }
}

void permutation::calculateFitness() {
  fitness = 0;
  for (auto i = this->begin() + 1; i < this->end(); ++i) {
    fitness += M[*i][*(i - 1)];
  }
  fitness += M[(*this)[0]][(*this)[this->size() - 1]];
}

bool permutation::operator<(const permutation &b) const {
  return (this->fitness > b.fitness);
}

int permutation::getFitness() {
  return fitness;
}

permutation::permutation() {
  this->resize(N);
  for (auto i = this->begin(); i != this->end(); ++i)
    *i = distance(this->begin(), i);
}

permutation::permutation(int) {
  this->resize(N);
  for (auto i = this->begin(); i != this->end(); ++i)
    *i = distance(this->begin(), i);
  random_shuffle(this->begin(), this->end());
}

void permutation::cross(permutation& b2)  {
  unsigned int seq0 = rand() % (this->size() - 1);
  unsigned int seq1 = rand() % (this->size() - seq0) + seq0 + 1;
  *aux = *this;
  memset(&(*aux0)[0], 0, N);
  for (unsigned int i = seq0; i != seq1; i++)
    (*aux0)[(*this)[i]] = 1;
  unsigned int j = (seq0 == 0) ? seq1 : 0;
  for (auto i = b2.begin(); i != b2.end(); ++i)
  if (!(*aux0)[*i]) {
    (*aux0)[*i] = 1;
    (*this)[j] = *i;
    j++;
    if (j == seq0) j = seq1;
  }
  memset(&(*aux0)[0], 0, N);
  for (unsigned int i = seq0; i != seq1; i++)
    (*aux0)[b2[i]] = 1;
  j = (seq0 == 0) ? seq1 : 0;
  for (auto i = (*aux).begin(); i != (*aux).end(); ++i)
  if (!(*aux0)[*i]) {
    (*aux0)[*i] = 1;
    b2[j] = *i;
    j++;
    if (j == seq0) j = seq1;
  }
}

permutation GA() {
  vector<permutation> v;
  v.reserve(N << 2);
  for (int i = 0; i < (N << 2); i++)
    v.push_back(permutation(0));
  int genNumber = 0;
  int bestSol = 0; bool haveSol = false;
  while (genNumber < MAX_GENERATIONS) {
    for (auto i = v.begin(); i != v.end(); ++i) {
      i->calculateFitness();
    }
    sort(v.begin(), v.end());
    bestSol = (haveSol) ? min(bestSol, (v.end() - 1)->getFitness()) : (v.end() - 1)->getFitness();
    haveSol = true;
    //printf("Generation %07d : best this generation %lf : best overall %lf\n", genNumber, (v.end() - 1)->getFitness(), bestSol);
    unsigned int replaced = 0;
    unsigned int noElemReplace = 1;
    unsigned int FACTOR = 2;
    while (replaced < (v.size() / FACTOR)) {
      for (unsigned int i = 0; i < noElemReplace && replaced < (v.size() / FACTOR); i++, replaced++)
        v[replaced] = v[v.size() - 1 - i]; //making mating pool
      noElemReplace++;
    }
    random_shuffle(v.begin(), v.end() - 2);
    for (auto i = v.begin(); i < v.end() - 2; i += 2)
      i->cross(*(i + 1));
    for (auto i = v.begin(); i < v.end() - 1; ++i)
      i->mutate();
    genNumber++;
  }
  return *(v.end() - 1);
}

void userInput() {
  scanf("%d", &N);
  permutation::aux = new permutation();
  permutation::aux0 = new vector<char>(N);
  for (int i = 0; i < N; ++i)
  for (int j = i; j < N; ++j)
    M[i][j] = M[j][i] = 10 * MAXCOST;
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    M[a][b] = c;
  }
}

int main() {
  srand(12445);
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  userInput();
  auto x = GA();
  printf("%d\n", x.getFitness());
  return 0;
}