// fara continue
// fara parametrul start.
// Fara for-ul care selecteaza ca nod initial fiecare nod.
// 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> A[MAXN];
int Cost[MAXN][MAXN];
int cd[MAXCONF][MAXN];

int cost_drum(int conf, int ultimul) {
    if (cd[conf][ultimul] == -1) { // trebuie calculat
        cd[conf][ultimul] = INF;   // initializam un minim
        for (int nod : A[ultimul])
            if (conf & (1 << nod)) { // nod se afla in configuratie
                // if (nod == 0 and ((conf ^ (1 << ultimul)) != 1)) // conditia initiala
                if (nod != 0 or ((conf ^ (1 << ultimul)) == 1))
                    cd[conf][ultimul] = min(cd[conf][ultimul], cost_drum(conf ^ (1 << ultimul), nod) + Cost[nod][ultimul]);
            }
    }
    return cd[conf][ultimul];
}

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