#include <fstream>
#include <cstring>

using namespace std;

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

const int f_mare = 2e9;
bool fol[20][20];
int ct[20][20], n, m, i, j, k;
int sol[280000][20], x, y, c;

int main() {
    f >> n >> m;
    while (m--) {
        f >> x >> y >> c;
        ct[x][y] = c;
        fol[x][y] = 1;
    }
    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))) {
                for (k = 0; k < n; k++)
                    if (k != j && (i&(1<<k)) && fol[k][j])
                        sol[i][j] = min(sol[i][j], sol[i^(1<<j)][k] + ct[k][j]);
            }
    }
    int minim = f_mare;
    for (i = 0; i < n; i++)
        if (fol[1][i])
            minim = min(minim, sol[(1<<n)-1][i]+ct[1][i]);
    if (minim != f_mare)
        g << minim;
    else g << "Nu exista solutie";
    return 0;
}