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

bool citire(std::vector<std::vector<int> > &graf, std::vector<std::vector<int> > &costGraf, int &n) {
    int m;
    int i, j, w;
    std::ifstream f("hamilton.in");
    f >> n >> m;
    graf.resize(n);
    costGraf.resize(n, std::vector<int>(n, 1e9));
    std::vector<int> grad(n);
    // TEOREMA LUI DIRAC: Intr-un graf cu n>=3 noduri, fiecare nod are grad(v)>=n/2 <=> graf hamiltonian.
    while (m--) {
        f >> i >> j >> w;
        graf[i].push_back(j);
        costGraf[i][j] = w;
        ++grad[j];
    }
    f.close();

    // verificam Teorema lui Dirac
    if (n >= 3)
        for (i = 0; i < n; ++i)
            if (grad[i] < n / 2)
                return false;
    return true;
}

void sol() {
    std::vector<std::vector<int> > graf;
    std::vector<std::vector<int> > costGraf;
    int n;
    if (!citire(graf, costGraf, n)) {
        std::ofstream g("hamilton.out");
        g << "Nu exista solutie";
        g.close();
        return;
    }

    const int nrSubmultimi = (1 << n) - 1;
    std::vector costLant(nrSubmultimi + 1, std::vector<int>(n, 1e9));
    costLant[1][0] = 0;
    // c[i][k] = costul minim al unui lant care incepe in nodul 0, se termina in nodul k si are nodurile intermediare
    // din multimea i (sir binar codificat de numarul i)
    // c[1][0] = 0

    for (int S = 1; S <= nrSubmultimi; ++S)
        // pentru fiecare submultime posibila de varfuri din lant
        for (int i = 0; i < n; ++i)
            // pentru fiecare nod din graf
            if (S & (1 << i))
                // daca nodul i face parte din multimea de noduri (daca nu face, cum putem avea lant de la 0 la i?)
                for (const auto j: graf[i])
                    if (!(S & (1 << j))) {
                        // daca vecinul j al lui i nu face parte din submultime
                        const int aux = S | (1 << j); // il bagam pe j in submultime (intr-o variabila auxiliara)
                        costLant[aux][j] = std::min(costLant[aux][j], costLant[S][i] + costGraf[i][j]);
                    }

    // am calculat doar lanturile
    // costul total al unui ciclu hamiltonian va fi lantul de la 0 la i (cu toate nodurile grafului) + costGraf[i][0]
    int costMin = 1e9;
    for (const auto &j: graf[0])
        costMin = std::min(costMin, costLant[nrSubmultimi][j] + costGraf[j][0]);

    std::ofstream g("hamilton.out");
    if (costMin == 1e9)
        g << "Nu exista solutie";
    else
        g << costMin;
    g.close();
}

int main() {
    sol();
    return 0;
}