// 100 p

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

using namespace std;

const int MAXN = 20;
const int MAXCONF = (1 << 18) + 1;
const int INF = 1e9;

int N, M, cost_ham;
vector<int> pred[MAXN];
int Cost[MAXN][MAXN];
int cd[MAXCONF][MAXN];

int cost_drum(int conf, int ultim) {
    if (cd[conf][ultim] == -1) { // Trebuie calculat.
        cd[conf][ultim] = INF;   // Initializam un minim.
        for (int nod : pred[ultim])
            if (conf & (1 << nod)) { // nod se afla in configuratie
                if (nod != 0 or ((conf ^ (1 << ultim)) == 1)) {
                    int cost_nod = cost_drum(conf ^ (1 << ultim), nod);
                    if (cd[conf][ultim] > cost_nod + Cost[nod][ultim])
                        cd[conf][ultim] = cost_nod + Cost[nod][ultim];
                }
            }
    }
    return cd[conf][ultim];
}

int main() {
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin >> N >> M;
    memset(Cost, 127, sizeof(Cost)); // 2.139.062.143
    for (int i = 1; i <= M; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        pred[y].push_back(x); // arcul invers
        Cost[x][y] = c;
    }
    cost_ham = INF;
    memset(cd, -1, sizeof(cd));
    cd[1][0] = 0;
    for (int nod : pred[0]) {
        int cost_vecin = cost_drum((1 << N) - 1, nod);
        if (cost_ham > cost_vecin + Cost[nod][0])
            cost_ham = cost_vecin + Cost[nod][0];
    }
    if (cost_ham != INF)
        fout << cost_ham << '\n';
    else
        fout << "Nu exista solutie" << '\n';
    return 0;
}