#include <fstream>

using namespace std;

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

int f_mare = 1500000002;
int C[20][20], x, y, c, n, m, i, j, w;
int sol[265000][20];
bool fol[20][20];

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