#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int NMAX = 20;
const int INF = (1<<30);

int N; int M; int cost[NMAX][NMAX];

int D[1 << NMAX][NMAX];


vector<int> father[NMAX];

void read() {

    fin >> N >> M;
    while(M--) {

        int x; int y; int c;
        fin >> x >> y >> c;
        father[y].push_back(x);
        cost[x][y] = c;

    }
}

int compute(int state, int last) {

    if(D[state][last] == -1) {
        D[state][last] = INF;

        for(unsigned i = 0 ; i < father[last].size(); ++i) {

            if(state & (1 << father[last][i])) {//trecem din nodul last, in father[last][i], deci trebuie sa fim in nodul last

                if(father[last][i] == 0 && state != (1 << last) + 1) continue;
                //nodul 1 incheie ciclul, deci nu trecem prin el dacat la final

                D[state][last] = min(D[state][last], compute(state ^ (1 << last), father[last][i]) + cost[father[last][i]][last]);
            }
        }
    }
    return D[state][last];
}

int main() {

    for(int i = 0; i <= N; ++i)
        for(int j = 0 ;j <= N; ++j)
            cost[i][j] = INF;

    read();

    int sol = INF;

    memset(D, -1, sizeof(D));

    D[1][0] = 0;

    for(unsigned i = 0 ;i < father[0].size(); ++i)
        sol = min(sol, compute( (1 << N) - 1 ,  father[0][i] ) + cost[father[0][i]][0]);

    if(sol == INF) fout <<"Nu exista solutie" <<'\n';
    else  fout << sol << '\n';

    return 0;
}