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

using namespace std;

const int INF = 1e9;
const int MAXN = 19; // Punem 19 pentru siguranta (N <= 18)

// dp[mask][i] = costul minim pentru a vizita nodurile din mask, terminand in i
int dp[1 << MAXN][MAXN];

// Matrice de adiacenta pentru a gestiona usor muchiile multiple (pastram minimul)
int cost[MAXN][MAXN];

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

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

    // 1. Initializare matrice de costuri cu INF
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cost[i][j] = INF;
        }
    }

    // 2. Citire si pastrarea muchiei minime intre oricare doua noduri
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        fin >> u >> v >> c;
        if (c < cost[u][v]) {
            cost[u][v] = c;
        }
    }

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

    // Pornim din nodul 0 -> masca este (1 << 0), adica 1
    dp[1][0] = 0;

    // 4. Iterare DP
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            // Daca am ajuns in starea 'mask' terminand in 'i' (si starea e valida)
            if ((mask & (1 << i)) && dp[mask][i] != INF) {

                // Incercam sa extindem catre un nod 'j' care NU este in mask
                for (int j = 0; j < n; ++j) {
                    // Verificam daca bitul j e 0 in masca si daca exista muchie i -> j
                    if (!(mask & (1 << j)) && cost[i][j] != INF) {
                        int next_mask = mask | (1 << j);

                        // Verificam daca am gasit un cost mai bun
                        if (dp[next_mask][j] > dp[mask][i] + cost[i][j]) {
                            dp[next_mask][j] = dp[mask][i] + cost[i][j];
                        }
                    }
                }
            }
        }
    }

    // 5. Calcul cost final (inchiderea ciclului catre nodul 0)
    int min_cycle = INF;
    int full_mask = (1 << n) - 1;

    // Verificam toate nodurile finale posibile 'i' din care ne putem intoarce in 0
    for (int i = 1; i < n; ++i) {
        if (dp[full_mask][i] != INF && cost[i][0] != INF) {
            int total = dp[full_mask][i] + cost[i][0];
            if (total < min_cycle) {
                min_cycle = total;
            }
        }
    }

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

    return 0;
}