#include<fstream>

using namespace std;

int h[19], c[18][18], n, m, x, y, i, smin, s;
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]; // inclusiv costul ultimei muchii
      if (sn < smin)
        if (k == n)
          smin = sn;
        else {
          v[i] = true;
          hamilton(k + 1, sn);
          v[i] = false;
        }
    }
  }
}

int main () {
  citire();
  smin = 18 * 1e6;
  hamilton(2, s);
  if (smin == 18 * 1e6)
    fout << "Nu exista solutie";
  else
    fout << smin;
}