#include <fstream>
#include <iostream>

using namespace std;

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

const int nmax = 18, f_mare = 2e9;
int n, m, i, j, k, x, y, c;
int sol[(1<<nmax)+7][nmax], ct[nmax][nmax];
bool posib[nmax][nmax];

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

    return 0;
}