#include <fstream>
#include <vector>

using namespace std;

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

const int f_mare = 1000000000;
vector <int> ls[20];
int n, m, x, y, c, i, j, I, k;
int cost[20][20], minim;
int sol[280000][20];

int main(){
    f >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            cost[i][j] = 0;

    while (m){
        f >> x >> y >> c;
        ls[y].push_back(x);
        cost[x][y] = c;
        m--;
    }
    for (i = 0; i < (1 << n); i++)
        for (j = 0; j < n; j++)
            sol[i][j] = f_mare;

    sol[1][0] = 0;
    for (i = 0; i < (1 << n); i++)
        for (j = 0; j < n; j++)
            if (i & (1 << j)){
                k = ls[j].size();
                for (I = 0; I < k; I++)
                    sol[i][j] = min(sol[i^(1 << j)][ ls[j][I] ] + cost[ ls[j][I] ][j], sol[i][j]);
            }

    minim = f_mare;
    k = ls[0].size();
    for (i = 0; i < k; i++)
        minim = min(minim, sol[(1 << n) - 1][ ls[0][i] ] + cost[ls[0][i]][0]);

    if (minim != f_mare) g << minim;
    else g << "Nu exista solutie";

    return 0;
}