// #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];
// //in graf avem lista de adiacenta + muchia asociata
//
// 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

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

void ReadInput() {
    ifstream fin("hamilton.in");
    fin>>N>>M;
    for (int i = 1; i <= M; i++) {
        int u,v,p;
        fin>>u>>v>>p;
        G[u].push_back(make_pair(v,p)); // noduri indexate de la 0
    }
    fin.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 arbitrar un nod de inceput pentru ciclul hamiltonian
    dp[0][1] = 0;
    //fiecare lant parcurs pentru a determina un lant hamiltonian poate fi reprezentat intern de 2 lucruri:
    //1.ultimul nod din 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 determiant 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 dac 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 primit 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 hamiltoniene de costuri minime in dp[x][11111111...], unde x apartine lui [0,n-1]
    int masca_biti_toate_noduri = (1<<N) -1;

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