#include <bits/stdc++.h>

using namespace std;

int main() {

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

    const int INF = 1e7;

    int n, m;
    in >> n >> m;

    vector<vector<int>> rg(n + 1);
    vector<vector<int>> cost(n + 1, vector<int>(n + 1, INF));
    for (int i = 1; i <= m; i++) {
        int x, y, c;
        in >> x >> y >> c;
        rg[y].push_back(x);
        cost[x][y] = c;
    }

    vector<vector<int>> dp(n + 1, vector<int>((1 << n) + 1, INF));
    dp[0][1] = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        for (int node = 0; node < n; node++) {
            // Checl of mask contains node
            if ((1 << node) & mask) {
                for (int neighbor : rg[node]) {
                    // If mask contains node's neighbor
                    if ((1 << neighbor) & mask) {
                        dp[node][mask] = min(dp[node][mask], dp[neighbor][mask ^ (1 << node)] + cost[neighbor][node]);
                    }
                }
            }
        }
    }

    int ans = INF;
    for (int neighbor : rg[0]) {
        ans = min(ans, dp[neighbor][(1 << n) - 1] + cost[neighbor][0]);
    }

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

    return 0;
}