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

using namespace std;

// Constante
const int INF = 1e9; // O valoare suficient de mare pentru infinit
const int MAXN = 18; // N maxim conform restricțiilor problemei (de obicei 18 sau 20)

// dp[mask][last_node]
// mask = configurația de biți a nodurilor vizitate
// last_node = ultimul nod vizitat
int dp[1 << MAXN][MAXN];

// Lista de adiacență: adj[nod] = vector de perechi {vecin, cost}
vector<pair<int, int>> adj[MAXN];

int main() {
    // Deschidem fișierele de intrare/ieșire
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");

    int n, m;
    fin >> n >> m;

    // Citim muchiile
    for (int i = 0; i < m; ++i) {
        int u, v, cost;
        fin >> u >> v >> cost;
        // Graful este orientat
        adj[u].push_back({v, cost});
    }

    // Inițializăm matricea DP cu INF
    for (int mask = 0; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            dp[mask][i] = INF;
        }
    }

    // Cazul de bază:
    // Începem din nodul 0. Masca inițială are doar bitul 0 setat (1 << 0),
    // iar ultimul nod vizitat este chiar 0. Costul este 0.
    dp[1][0] = 0;

    // Iterăm prin toate măștile posibile
    // Deoarece adăugăm noduri, noua mască va fi mereu mai mare numeric decât cea veche,
    // deci putem itera liniar de la 1 la (1<<n)-1.
    for (int mask = 1; mask < (1 << n); ++mask) {
        // Iterăm prin toate nodurile i care ar putea fi ultimul nod vizitat în această mască
        for (int i = 0; i < n; ++i) {
            // Verificăm dacă nodul i face parte din mască și dacă starea este validă (accesibilă)
            if ((mask & (1 << i)) && dp[mask][i] != INF) {

                // Încercăm să extindem drumul către toți vecinii lui i
                for (auto& edge : adj[i]) {
                    int next_node = edge.first;
                    int cost = edge.second;

                    // Verificăm dacă next_node NU a fost deja vizitat în masca curentă
                    if (!(mask & (1 << next_node))) {
                        int next_mask = mask | (1 << next_node);

                        // Relaxarea muchiei (actualizăm minimul)
                        if (dp[next_mask][next_node] > dp[mask][i] + cost) {
                            dp[next_mask][next_node] = dp[mask][i] + cost;
                        }
                    }
                }
            }
        }
    }

    // Calculăm costul minim pentru a închide ciclul
    // Masca finală trebuie să aibă toți biții setați: (1 << n) - 1
    int full_mask = (1 << n) - 1;
    int min_cycle_cost = INF;

    // Verificăm toate nodurile i care pot fi finalul unui drum Hamiltonian
    // și vedem dacă putem reveni în nodul 0
    for (int i = 1; i < n; ++i) {
        if (dp[full_mask][i] != INF) {
            // Căutăm dacă există muchie de la i la 0
            for (auto& edge : adj[i]) {
                if (edge.first == 0) {
                    int current_total = dp[full_mask][i] + edge.second;
                    if (current_total < min_cycle_cost) {
                        min_cycle_cost = current_total;
                    }
                }
            }
        }
    }

    // Afișăm rezultatul
    if (min_cycle_cost == INF) {
        fout << "Nu exista" << endl;
    } else {
        fout << min_cycle_cost << endl;
    }

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

    return 0;
}