#include <bits/stdc++.h>
#include <fstream>
using namespace std;

const int NMAX = 18;

int N, M;
vector<pair<int, int>> G[NMAX]; 
// lista de adiacenta cu ponderi (costuri)

int dp[NMAX][(1 << NMAX)]; // tabela pentru stari Ciclu Hamiltonian
// costul minim ciclu hamiltonian
// 2^N = (1 << N)
// lantul hamiltonian de cost dp[i][j]


void ReadInput() {
    ifstream f("hamilton.in");
    f >> N >> M;
    for (int i = 1; i <= M; i++) {
        int u, v, p;
        f >> u >> v >> p;
        G[u].push_back({v, p}); // noduri indexate de la 0
    }
    f.close();
}

void SolveCicluHamiltonian() {
    // Initializare Tabela pentru stari
    for (int i = 0; i < N; i++) // ultimul_nod
        for (int j = 0; j < (1 << N); j++) // masca de biti
            dp[i][j] = INT_MAX;
    // alegem arbitrat un nod de inceput pentru ciclul hamiltonian
    
    dp[0][1] = 0;
    // fiecare lant parcurs pentru a determina un lant hamilton poate fi reprezentat intern de 2 lucruri:
    // 1. ultimul nod in lant
    // 2. masca de biti a nodurilor parcurse 

    // 2 3 1 0
    // 3 2 1 0
    // ne folosim de programare dinamica pentru ca un lant nu este unic determinat de cele 2 elemente de sus 
    // calculam la fiecare pas minimul costului pentru lantul hamiltonian

    for (int masca = 0; masca < (1 << N); masca++)
        for (int ultimul_nod = 0; ultimul_nod < N; ultimul_nod++) {
            // determinam daca este este continut in masca de biti
            if ((masca & (1 << ultimul_nod)) > 0) {
                for (auto [nod_nou, pond] : G[ultimul_nod]) {
                    // determinam daca nu este continut in masca de biti
                    if ((masca & (1 << nod_nou)) == 0) {
                        // ca sa nu primim overflow verificam daca chiar putem avea starea [ultimul_nod, masca]
                        if (dp[ultimul_nod][masca] == INT_MAX)
                            continue;

                        // nodul nou are o muchie cu ultimul nod din lant
                        dp[nod_nou][masca + (1 << nod_nou)] = min(dp[nod_nou][masca + (1 << nod_nou)],
                                                                  dp[ultimul_nod][masca] + pond);
                    }
                }
            }
        }
    
    // Am determinat lanturile hamiltoniane de costuri minime in dp[X][11111111111...], unde X apartine lui [0, N - 1]
    int masca_biti_toate_noduri = (1 << N) - 1;

    // Determinam ciclul hamiltonian de cost minim
    int Min = INT_MAX;
    for (int ultimul_nod = 0; ultimul_nod < N; ultimul_nod++)
        for (auto [vecin, pond] : G[ultimul_nod])
            if (vecin == 0 && dp[ultimul_nod][masca_biti_toate_noduri] != INT_MAX)
                Min = min(Min, dp[ultimul_nod][masca_biti_toate_noduri] + pond);
        
    ofstream g("hamilton.out");
    if (Min == INT_MAX)
        g << "Nu exista solutie";
    else g << Min;

    g.close();

}

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