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

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

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

int N, M;
vector<int> incoming[MAX_N];
int cost[MAX_N][MAX_N];
int best[1 << MAX_N][MAX_N];

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

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cost[i][j] = INF;
        }
    }

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

    for (int conf = 0; conf < (1 << N); ++conf) {
        for (int j = 0; j < N; ++j) {
            best[conf][j] = INF;
        }
    }

    best[1][0] = 0;
    for (int conf = 0; conf < (1 << N); ++conf) {
        for (int j = 0; j < N; ++j) {
            if ((1 << j) & conf) {
                for (auto i: incoming[j]) {
                    if ((1 << i) & conf) {
                        best[conf][j] = min(best[conf][j], best[conf ^ (1 << j)][i] + cost[i][j]);
                    }
                }
            }
        }
    }

    int answer = INF;
    for (auto i: incoming[0]) {
        answer = min(answer, best[(1 << N) - 1][i] + cost[i][0]);
    }

    if (answer == INF) {
        fout << "Nu exista solutie\n";
    }
    fout << answer;

    return 0;
}