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

using namespace std;

// Folosim long long pentru a evita overflow cand se aduna costurile
// INF trebuie sa fie mai mare decat orice suma posibila de costuri
const long long INF = 1e18;
const int MAXN = 19; // N <= 18

// dp[mask][i] = costul minim
// Folosim long long aici!
// Dimensiune: (1<<19) * 19 * 8 bytes ~= 80 MB. E mult, dar Infoarena da de obicei 64MB+.
// Daca memoria e limita stricta (ex 32MB), revenim la int dar cu grija la overflow.
// Totusi, testele tale arata 20MB usage pe int. Cu long long va fi ~40MB. E safe.
long long dp[1 << MAXN][MAXN];

// Lista de adiacenta: adj[nod] = {vecin, cost}
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});
    }

    // Initializare DP
    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            dp[mask][i] = INF;
        }
    }

    // Cazul de baza: pornim din 0, cost 0
    dp[1][0] = 0;

    // Iteram prin toate mastile
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            // Daca starea curenta e valida
            if ((mask & (1 << i)) && dp[mask][i] != INF) {

                // Iteram doar prin vecinii existenti (eficienta pt grafuri rare)
                for (auto& edge : adj[i]) {
                    int vec = edge.first;
                    int cost = edge.second;

                    // Daca vecinul NU e in masca curenta
                    if (!(mask & (1 << vec))) {
                        int next_mask = mask | (1 << vec);

                        // Relaxare
                        if (dp[next_mask][vec] > dp[mask][i] + cost) {
                            dp[next_mask][vec] = dp[mask][i] + cost;
                        }
                    }
                }
            }
        }
    }

    // Calculam raspunsul final
    long long min_cycle = INF;
    int full_mask = (1 << n) - 1;

    // Verificam intoarcerea din fiecare nod posibil i inapoi in 0
    for (int i = 1; i < n; ++i) {
        if (dp[full_mask][i] != INF) {
            // Cautam muchia i -> 0
            for (auto& edge : adj[i]) {
                if (edge.first == 0) {
                    // Atentie: dp este long long, cost este int, suma e safe
                    long long current_total = dp[full_mask][i] + edge.second;
                    if (current_total < min_cycle) {
                        min_cycle = current_total;
                    }
                }
            }
        }
    }

    if (min_cycle == INF) {
        fout << "Nu exista" << endl;
    } else {
        fout << min_cycle << endl;
    }

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

    return 0;
}