#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

const int N = 22, cm = (1 << 22), inf = (1 << 30);

int a[N][N], C[cm][N], sol, conf, i, j, n, m, x, y;

int back(int x, int conf) {
    if (C[conf][x] == -1) {
        C[conf][x] = inf;
        for (int i = 1, p = 1; i <= n; i++, p <<= 1) {
            if ((conf & p) && a[i][x]) {
                if (i == 1 && conf != (1 << (x - 1)) + 1) {
                    continue;
                }
                C[conf][x] = min(C[conf][x], back(i, conf - (1 << (x - 1))) + a[i][x]);
            }
        }
    }
    return C[conf][x];
}

int main () {
    fin >> n >> m;
    for (i = 1; i <= m; ++i) {
        fin >> x >> y;
        x++;
        y++;
        fin >> a[x][y];
    }
    sol = inf;
    conf = (1 << n) - 1;
    for (i = 1; i <= conf; ++i) {
        memset(C[i], -1, sizeof(C[i]));
    }
    C[1][1] = 0;
    for (i = 2; i <= n; ++i) {
        if(a[i][1]) {
            sol = min(sol, back(i, conf) + a[i][1]);
        }
    }
    if (sol < inf) {
        fout << sol;
        return 0;
    } else {
        fout << "Nu exista solutie";
    }
    return 0;
}