// #include <algorithm>
// #include <iostream>
// #include <fstream>
// #include <vector>
//
// using namespace std;
//
// const int NMAX= 100'000;
// const int MMAX = 500'000;
//
// int N,M;
//
// vector<pair<int,int>> G[NMAX +1];
//
// ofstream fout("ciclueuler.out");
//
// void ReadInput() {
//     ifstream fin("ciclueuler.in");
//     fin>>N>>M;
//     for(int i=1;i<=M;i++) {
//         int u,v;
//         fin>>u>>v;
//         G[u].push_back(make_pair(v,i));
//         G[v].push_back(make_pair(u,i));
//     }
//     fin.close();
// }
//
// bool visited[MMAX+1];
// vector<int> ciclu_eulerian;
//
// void FleuryAlgorithm(int nod) {
//     while (G[nod].size() > 0) {
//         auto [vecin, ind_muchie] = G[nod].back();
//         G[nod].pop_back();
//         if (visited[ind_muchie] == 1) continue;
//         visited[ind_muchie] = 1;
//         FleuryAlgorithm(vecin);
//         ciclu_eulerian.push_back(vecin);
//     }
// }
//
// void solveCicluEulerian() {
//     for (int i = 1; i <= M ;i++) {
//         visited[i] = 0;
//     }
//     ciclu_eulerian.clear();
//     FleuryAlgorithm(1);
//
//     bool single_connected_component = true;
//     for (int i = 1; i <= M; i++) {
//         if (visited[i] == 0) {
//             single_connected_component = false;
//         }
//     }
//     if (single_connected_component == false)
//         fout<<-1;
//     else {
//         for (int nod: ciclu_eulerian) {
//             fout<<nod<<" ";
//         }
//     }
// }
//
// int main() {
//     ReadInput();
//
//     bool grade_pare = true;
//     for (int i = 1; i <= N; i++) {
//         if (G[i].size() %2 != 0) {
//             grade_pare = false;
//         }
//     }
//     if (grade_pare == false) fout<<-1;
//     else solveCicluEulerian();
//     return 0;
// }

#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;
}