// 70 p infoarena
#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;
}