// Incercare 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, Sol;
vector<int> A[MAXN];
int Cost[MAXN][MAXN];
int C[MAXCONF][MAXN];

int calc(int conf, int ultimul) {
    if (C[conf][ultimul] == -1) { // trebuie calculat
        C[conf][ultimul] = INF;   // initializam un minim
        for (int nod : A[ultimul])
            if (conf & (1 << nod)) { // nod se afla in configuratie
                if (nod == 0 && ((conf ^ (1 << ultimul)) != 1))
                    continue;
                C[conf][ultimul] = min(C[conf][ultimul], calc(conf ^ (1 << ultimul), nod) + Cost[nod][ultimul]);
            }
    }
    return C[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;
    }
    Sol = INF;
    memset(C, -1, sizeof(C));
    C[1][0] = 0;
    for (int vecin : A[0]) 
        Sol = min(Sol, calc((1 << N) - 1, vecin) + Cost[vecin][0]);
    if (Sol != INF)
        fout << Sol << endl;
    else
        fout << "Nu exista solutie" << endl;
    return 0;
}