#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    const long long INF = (1LL<<62);
    vector<vector<long long>> cost(N, vector<long long>(N, INF));
    for (int i = 0; i < M; ++i) {
        int x, y; long long c;
        cin >> x >> y >> c;
        cost[x][y] = c;
    }

    int start = 0;
    int FULL = (1 << N) - 1;
    vector<vector<long long>> dp(1 << N, vector<long long>(N, INF));
    dp[1 << start][start] = 0;

    for (int mask = 1; mask <= FULL; ++mask) {
        if (!(mask & (1 << start))) continue;
        for (int v = 0; v < N; ++v) {
            if (!(mask & (1 << v))) continue;
            if (v == start && mask != (1 << start)) continue;
            long long best = dp[mask][v];
            int prevMask = mask ^ (1 << v);
            if (prevMask == 0) continue;
            for (int u = 0; u < N; ++u) {
                if (!(prevMask & (1 << u))) continue;
                if (cost[u][v] == INF) continue;
                long long cand = dp[prevMask][u] + cost[u][v];
                if (cand < best) best = cand;
            }
            dp[mask][v] = best;
        }
    }

    long long ans = INF;
    for (int v = 0; v < N; ++v) {
        if (v == start) continue;
        if (cost[v][start] == INF) continue;
        long long cand = dp[FULL][v] + cost[v][start];
        if (cand < ans) ans = cand;
    }

    if (ans >= INF/2) {
        cout << "Nu exista solutie\n";
    } else {
        cout << ans << "\n";
    }
    return 0;
}