#include <fstream>
#include <vector>
#include <queue>
#include <limits>
#include <bitset>

using namespace std;
ifstream  fin("hamilton.in");
ofstream fout("hamilton.out");
const int INF = 1e9;
int n,m;  // numărul de noduri
vector<vector<int>> cost;  // matricea de costuri

struct Nod {
    int pozitie;         // nodul curent
    int costCurent;      // cost acumulat
    int costEstimare;    // cost total estimat (cu euristică)
    int vizitate;        // bitmask pentru noduri vizitate
    vector<int> drum;    // drumul parcurs până acum

    bool operator<(const Nod& alt) const {
        return costEstimare > alt.costEstimare;  // coadă de priorități min-heap
    }
};

// euristică simplă: suma celor mai mici muchii pentru nodurile nevizitate
int estimeazaCost(int pozitie, int vizitate) {
    int estimare = 0;
    for (int i = 0; i < n; i++) {
        if (!(vizitate & (1 << i))) {
            int minCost = INF;
            for (int j = 0; j < n; j++) {
                if (i != j) minCost = min(minCost, cost[i][j]);
            }
            estimare += minCost;
        }
    }
    // adăugăm un cost minim de întoarcere la start
    int minBack = INF;
    for (int i = 0; i < n; i++) {
        if (!(vizitate & (1 << i))) {
            minBack = min(minBack, cost[pozitie][i]);
        }
    }
    return estimare + (minBack == INF ? 0 : minBack);
}

pair<vector<int>, int> branchAndBoundTSP() {
    priority_queue<Nod> pq;

    int vizStart = 1 << 0;
    pq.push({0, 0, estimeazaCost(0, vizStart), vizStart, {0}});

    int costMinim = INF;
    vector<int> drumMinim;

    while (!pq.empty()) {
        Nod curent = pq.top();
        pq.pop();

        // dacă am vizitat toate nodurile
        if (curent.vizitate == (1 << n) - 1) {
            int totalCost = curent.costCurent + cost[curent.pozitie][0];  // închide ciclul
            if (totalCost < costMinim) {
                costMinim = totalCost;
                drumMinim = curent.drum;
                drumMinim.push_back(0);  // închidere ciclu
            }
            continue;
        }

        // extindem spre noduri nevizitate
        for (int i = 0; i < n; i++) {
            if (!(curent.vizitate & (1 << i))) {
                int nouCost = curent.costCurent + cost[curent.pozitie][i];
                int vizNou = curent.vizitate | (1 << i);
                int estimare = nouCost + estimeazaCost(i, vizNou);

                if (estimare < costMinim) {
                    vector<int> nouDrum = curent.drum;
                    nouDrum.push_back(i);
                    pq.push({i, nouCost, estimare, vizNou, nouDrum});
                }
            }
        }
    }

    return {drumMinim, costMinim};
}

int main() {

    fin >> n >> m;
    cost.assign(n, vector<int>(n));

    ///cout << "Introdu matricea de costuri (" << n << "x" << n << "):\n";
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            ///fin >> cost[i][j];
            cost[i][j]=INF;
        }
        cost[i][i]=0;
    }
    for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        cost[x][y]=c;
    }
    auto [drum, costTotal] = branchAndBoundTSP();

    ///cout << "\nCiclu Hamiltonian de cost minim:\n";
    ///for (int nod : drum) cout << nod << " ";
    ///cout << "\nCost total: " ;
    fout << costTotal << endl;

    return 0;
}