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

const int nax = 18;
const int max_size = 1 << 18;

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

int n, m, adj[nax][nax];
vector<vector<int>> dp(max_size, vector<int>(nax, 2e9));
// dp[mask][last] - raspunsul problemei daca procesam doar nodurile care apartin multimii codificate de mask,
//                  parcurgand ultima data nodul cu indicele last din mask 

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    in >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int x, y, cost;
        in >> x >> y >> cost;
        adj[x][y] = cost;
    }
    // costurile sunt >= 1, deci daca adj[x][y] = 0, nu exista muchie de la x la y
    dp[1][0] = 0;
    for(int mask = 1; mask < (1 << n); ++mask) {
        for(int node = 0; node < n; ++node) {
            if(mask & (1 << node)) {
                // node - nodurile care fac parte din multimea codificata de mask 
                for(int neigh = 0; neigh < n; ++neigh) {
                    if(!adj[node][neigh] || (mask & (1 << neigh))) {
                        continue;
                    }
                    // daca neigh este adiacent cu node si nu este inca inclus in nodurile procesate
                    int next_mask = mask ^ (1 << neigh);
                    dp[next_mask][neigh] = min(dp[next_mask][neigh], dp[mask][node] + adj[node][neigh]);
                }
            }
        }
    }
    int answer = 2e9;
    for(int last_node = 0; last_node < n; ++last_node) {
        if(!adj[last_node][0]) {
            continue;
        }
        answer = min(answer, dp[(1 << n) - 1][last_node] + adj[last_node][0]);
    }

    if (answer == 2e9) {
        out << "Nu exista solutie\n";
        return 0;
    }

    out << answer << '\n';
    return 0;
}