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

using namespace std;

const int NMAX = 18;
const int INF = numeric_limits<int>::max();

int n, m;
int cost[NMAX][NMAX];
bool exists[NMAX][NMAX];
int dp[1 << NMAX][NMAX];

void citire() {
    ifstream fin("hamilton.in");
    fin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cost[i][j] = INF;
            exists[i][j] = false;
        }
    }
    for (int i = 0; i < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
        exists[x][y] = true;
    }
    fin.close();
}

void solve() {
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            dp[mask][i] = INF;
        }
    }
    for (int i = 0; i < n; i++) {
        dp[1 << i][i] = 0;
    }
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (dp[mask][i] == INF) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) {
                    continue;
                }
                if (!exists[i][j]) {
                    continue;
                }
                dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + cost[i][j]);
            }
        }
    }
    int minCost = INF;
    for (int i = 0; i < n; i++) {
        if (exists[i][0]) {
            minCost = min(minCost, dp[(1 << n) - 1][i] + cost[i][0]);
        }
    }
    if (minCost == INF) {
        ofstream fout("hamilton.out");
        fout << "Nu exista solutie";
        fout.close();
    } else {
        ofstream fout("hamilton.out");
        fout << minCost;
        fout.close();
    }
}

int main() {
    citire();
    solve();
    return 0;
}