#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;

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

const int INF = 1 << 30;
const int MAX_N = 20;

int N, M;
vector<int> from[MAX_N];
int cost[MAX_N][MAX_N];
int d[1 << MAX_N][MAX_N];

int main() {
    fin >> N >> M;
    for (int i = 0, a, b, c; i < M; i += 1) {
        fin >> a >> b >> c;
        from[b].push_back(a);
        cost[a][b] = c;
    }

    for (int mask = 0; mask < (1 << N); mask += 1) {
        for (int i = 0; i < N; i += 1) {
            d[mask][i] = INF;
        }
    }

    d[1][0] = 0;
    for (int mask = 0; mask < (1 << N); mask += 1) {
        for (int i = 0; i < N; i += 1) {
            if (!((1 << i) & mask)) continue;
            for (auto j: from[i]) {
                if (!((1 << j) & mask)) continue;
                d[mask][i] = min(d[mask][i], d[mask ^ (1 << i)][j] + cost[j][i]);
            }
        }
    }

    int result = INF;
    for (auto i: from[0]) {
        result = min(result, d[(1 << N) - 1][i] + cost[i][0]);
    }

    if (result == INF) {
        fout << "Nu exista solutie";
    } else {
        fout << result;
    }
    return 0;
}