#include <fstream>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int nmax = 18;
const unsigned f_mare = 4e9;
unsigned sol[(1<<nmax)][nmax], minim;
int c[nmax][nmax], n, m, k, i, j, x, y, z;

int main() {
    f >> n >> m;
    while (m--) {
        f >> x >> y >> z;
        c[x][y] = z;
    }
    for (i = 1; i < (1<<n); i++)
        for (j = 0; j < n; j++)
            sol[i][j] = f_mare;

    sol[1][0] = 0;

    for (i = 1; i < (1<<n); i++)
        for (j = 0; j < n; j++)
            if ((i&(1<<j))!=0)
                for (k = 0; k < n; k++)
                    if (k != j && (i&(1<<k))!=0 && c[k][j])
                        sol[i][j] = min(sol[i][j], sol[i^(1<<j)][k] + c[k][j]);

    minim = f_mare;
    for (i = 1; i < n; i++)
        if (c[i][0])
            minim = min(minim, sol[(1<<n)-1][i] + c[i][0]);
    if (minim != f_mare)
        g << minim;
    else g << "Nu exista solutie";

    return 0;
}