#include <fstream>

using namespace std;

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

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

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