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

using namespace std;

const int INF = 1e9;
const int MAXN = 18;
int dp[1 << MAXN][MAXN];
vector<pair<int, int>> adj[MAXN]; 

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

    int N, M;
    fin >> N >> M;

    for (int i = 0; i < M; ++i) {
        int u, v, c;
        fin >> u >> v >> c;
        adj[u].push_back({v, c});
    }

    for (int s = 0; s < (1 << N); ++s) {
        for (int i = 0; i < N; ++i) {
            dp[s][i] = INF;
        }
    }

    dp[1][0] = 0;

    for (int s = 1; s < (1 << N); s += 2) {
        for (int i = 0; i < N; ++i) {
            if ((s & (1 << i)) && dp[s][i] != INF) {
                for (auto& edge : adj[i]) {
                    int j = edge.first;
                    int cost = edge.second;
                    
                    if (!(s & (1 << j))) {
                        int next_s = s | (1 << j);
                        if (dp[next_s][j] > dp[s][i] + cost) {
                            dp[next_s][j] = dp[s][i] + cost;
                        }
                    }
                }
            }
        }
    }

    int min_cost = INF;
    int full_mask = (1 << N) - 1;

    for (int i = 1; i < N; ++i) {
        if (dp[full_mask][i] != INF) {
            for (auto& edge : adj[i]) {
                if (edge.first == 0) { 
                    if (min_cost > dp[full_mask][i] + edge.second) {
                        min_cost = dp[full_mask][i] + edge.second;
                    }
                }
            }
        }
    }

    if (min_cost == INF) {
        fout << "Nu exista solutie";
    } else {
        fout << min_cost;
    }

    fin.close();
    fout.close();

    return 0;
}