#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int N_MAX = 20;
const int X_MAX = 262150;
const int INF = 1000000000;

int N, M;
int Cost[N_MAX][N_MAX];
int C[X_MAX][N_MAX];  //in C[n][i] se retine costul unui lant ce se termina in i si contine nodurile coresp. bitilor de 1 ai lui n
vector<int> Inv_Edges[N_MAX];

int compute(int config, int last) {
    if (C[config][last] == -1) {
        C[config][last] = INF;
        for (auto x : Inv_Edges[last])  //parcurgem nodurile din lant care se duc in last
            if (config & (1 << x)) {
                if (x == 0 && config != (1 << last) + 1)  //nodul de start il scoatem ultimul
                    continue;
                C[config][last] = min(C[config][last], compute(config ^ (1 << last), x) + Cost[x][last]);
            }
    }
    return C[config][last];
}

int main() {
    in >> N >> M;

    //initializare
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            Cost[i][j] = INF;
    for (int i = 0; i < X_MAX; ++i)
        for (int j = 0; j < N; ++j)
            C[i][j] = -1;
    C[1][0] = 0;

    int x, y;
    for (int i = 0; i < M; ++i) {
        in >> x >> y;
        in >> Cost[x][y];
        Inv_Edges[y].push_back(x);  //retinem arcul opus
    }

    //ciclul porneste din nodul 0 (nu conteaza din ce nod porneste)
    int sol = INF;
    for (auto x : Inv_Edges[0])
        sol = min(sol, compute((1 << N) - 1, x) + Cost[x][0]);

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

    return 0;
}