// Incercare fara for-ul care selecteaza ca nod initial fiecare nod.
// 70 p

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

using namespace std;

const int MAXN = 20;
const int MAXX = 262150;
const int INF = 100000000;

int N, M, Sol;
vector<int> A[MAXN];
int Cost[MAXN][MAXN];
int C[MAXX][MAXN];

int calc(int start, int conf, int last) {
    if (C[conf][last] == -1) { // trebuie calculat
        C[conf][last] = INF;   // initializam un minim
        for (int nod : A[last]) {
            if (conf & (1 << nod)) { // nod se afla in configuratie
                if (nod == start && ((conf ^ (1 << last)) != (1 << start)))
                    continue;
                C[conf][last] = min(C[conf][last], calc(start, conf ^ (1 << last), nod) + Cost[nod][last]);
            }
        }
    }
    return C[conf][last];
}

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] = 0;
    for (size_t j = 0; j < A[0].size(); ++j)
        Sol = min(Sol, calc(0, (1 << N) - 1, A[0][j]) + Cost[A[0][j]][i]);
    if (Sol != INF)
        fout << Sol << endl;
    else
        fout << "Nu exista solutie" << endl;
    return 0;
}