#include<fstream>
#include<cstring>

using namespace std;

int h[19], c[18][18], d[18][18], n, m, x, y, i, j, k, smin, s, sc;
bool v[10];
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

void citire() {
  fin >> n >> m;
  for (i = 1; i <= m; i++) {
    fin >> x >> y;
    fin >> c[x][y];
  }
}

bool valid (int k) {
  if (v[h[k]])
    return false;
  else
    if (k <= n - 1)
      return c[h[k - 1]][h[k]] > 0;
    else
      return c[h[k - 1]][h[k]] > 0 and c[h[k]][0] > 0;
}

void hamilton (int k, int s) {
  int sn;
  for (int i = 1; i <= n - 1; i++) {
    h[k] = i;
    if (valid(k)) {
      sn = s + c[h[k - 1]][h[k]];
      if (k == n)
        sn += c[h[k]][0], sc = sn; // inclusiv costul ultimei muchii
      else
        sc = sn + d[h[k]][0]; // suma de comparat
      if (sc < smin)
        if (k == n)
          smin = sn;
        else {
          v[i] = true;
          hamilton(k + 1, sn);
          v[i] = false;
        }
    }
  }
}

int main () {
  citire();
  memcpy (d, c, sizeof d);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) {
      if (d[i][j] == 0)
        d[i][j] = 18 * 1e6;
    }
  for (k = 1; k <= n; k++) {
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        if (i != j && d[i][k] + d[k][j] < d[i][j])
          d[i][j] = d[i][k] + d[k][j];
  }
  smin = 18 * 1e6;
  hamilton(2, s);
  if (smin == 18 * 1e6)
    fout << "Nu exista solutie";
  else
    fout << smin;
}