#include <bits/stdc++.h>
#include <fstream>

using namespace std;

const int NMAX = 18;

int N, M;
vector<pair<int, int>> G[18];

void ReadInput() {
    ifstream f("hamilton.in");
    f >> N >> M;
    for (int i = 1; i <= M; i++) {
        int x, y, p;
        f >> x >> y >> p;
        G[x].push_back({y, p});
    }
    f.close();
}

int dp[NMAX][(1 << NMAX)]; // matrice tabelara pentru state-ul curent
// Prima dimensiune = ultimul_nod_parcurs
// A doua dimensiune = masca de biti asociate -> 2^N valori
// determina un lant hamiltonain

void SolveCicluHamiltonian() {
    // Initializam tabela cu maximul posibil (pentru ca noi vrem sa determinam costul minim)
    for (int i = 0; i < N; i++)
        for (int j = 0; j < (1 << N); j++)
            dp[i][j] = INT_MAX;

    dp[0][1] = 0; // 1 * 2^0 + 0 * 2^1 + 0 * 2^2 + 0 * ...

    // determinam ciclul hamiltonian de cost minim
    for (int masca = 0; masca < (1 << N); masca++) {
        // masca asociata -> contine anumite noduri
        for (int ultimul_nod = 0; ultimul_nod < N; ultimul_nod++) 
            if (masca & (1 << ultimul_nod)) { // apartine mastii
                for (auto [nod_nou, pond] : G[ultimul_nod]) {
                    if (!(masca & (1 << nod_nou))) {
                        if (dp[ultimul_nod][masca] == INT_MAX)
                            continue;
                        dp[nod_nou][masca + (1 << nod_nou)] = min(dp[nod_nou][masca + (1 << nod_nou)],
                                                                  dp[ultimul_nod][masca] + pond);
                    }
                }
            }
    }

    // masca (1 << N) - 1 contine toate nodurile

    // Verificam solutiile
    int Min = INT_MAX;
    for (int nod_final = 0; nod_final < N; nod_final++)
        for (auto [nod_vecin, pond] : G[nod_final]) {
            if (nod_vecin == 0 && dp[nod_final][(1 << N) - 1] != INT_MAX)
                Min = min(Min, dp[nod_final][(1 << N) - 1] + pond);
        }

    ofstream g("hamilton.out");
    if (Min == INT_MAX)
        g << "Nu exista solutie\n";
    else g << Min;
    g.close();
}

int main() {
    ReadInput();
    SolveCicluHamiltonian();
    return 0;
}