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

static const long long INF = (1LL << 60);

struct Edge {
    int to;
    int cost;
};

static mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> cost(N, vector<int>(N, -1));
    vector<vector<Edge>> g(N);

    for (int i = 0; i < M; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        cost[x][y] = c;
        g[x].push_back({y, c});
    }

    // Caz trivial
    if (N == 1) {
        if (cost[0][0] != -1) cout << cost[0][0] << "\n";
        else cout << "Nu exista solutie\n";
        return 0;
    }

    // Verificare rapidă: fiecare nod trebuie să aibă cel puțin o ieșire și o intrare,
    // altfel nu poate exista ciclu hamiltonian.
    vector<int> indeg(N, 0), outdeg(N, 0);
    for (int i = 0; i < N; i++) {
        for (auto &e : g[i]) {
            outdeg[i]++;
            indeg[e.to]++;
        }
    }
    for (int i = 0; i < N; i++) {
        if (indeg[i] == 0 || outdeg[i] == 0) {
            cout << "Nu exista solutie\n";
            return 0;
        }
    }

    // ACO parameters
    const int START = 0;
    const int ANTS = max(60, 8 * N);
    const int EPOCHS = 5000;          // multe epoci, conform cerinței
    const double ALPHA = 1.2;          // influența feromonului
    const double BETA = 4.0;           // influența euristicii 1/cost
    const double EVAP = 0.10;          // evaporare
    const double Q = 2000.0;           // cantitatea depusă
    const double ELITIST = 2.5;        // bonus pentru best global
    const double EPS = 1e-12;

    // Pheromone + heuristic
    vector<vector<double>> pher(N, vector<double>(N, 0.0));
    vector<vector<double>> desir(N, vector<double>(N, 0.0));

    for (int i = 0; i < N; i++) {
        for (auto &e : g[i]) {
            pher[i][e.to] = 1.0;
            desir[i][e.to] = 1.0 / max(1, e.cost);
        }
    }

    long long globalBest = INF;
    vector<int> globalPath;

    auto pathCost = [&](const vector<int>& path) -> long long {
        long long s = 0;
        for (int i = 0; i + 1 < (int)path.size(); i++) {
            int u = path[i], v = path[i + 1];
            if (cost[u][v] == -1) return INF;
            s += cost[u][v];
        }
        return s;
    };

    auto nearestCompletion = [&](vector<int>& path, vector<int>& used, int current) -> bool {
        // Completează greedy drumul când construcția probabilistică se blochează.
        for (int step = (int)path.size(); step < N; step++) {
            int nxt = -1;
            int bestC = INT_MAX;
            for (auto &e : g[current]) {
                if (!used[e.to] && e.cost < bestC) {
                    bestC = e.cost;
                    nxt = e.to;
                }
            }
            if (nxt == -1) return false;
            used[nxt] = 1;
            path.push_back(nxt);
            current = nxt;
        }
        if (cost[current][START] == -1) return false;
        path.push_back(START);
        return true;
    };

    auto constructAnt = [&]() -> pair<long long, vector<int>> {
        vector<int> used(N, 0);
        vector<int> path;
        path.reserve(N + 1);

        int current = START;
        used[current] = 1;
        path.push_back(current);

        for (int step = 1; step < N; step++) {
            vector<pair<int, double>> cand;
            cand.reserve(g[current].size());

            double total = 0.0;
            for (auto &e : g[current]) {
                if (used[e.to]) continue;

                double tau = pow(max(pher[current][e.to], EPS), ALPHA);
                double eta = pow(max(desir[current][e.to], EPS), BETA);
                double score = tau * eta;
                if (score > 0) {
                    cand.push_back({e.to, score});
                    total += score;
                }
            }

            if (cand.empty()) {
                // încearcă să completeze greedy
                bool ok = nearestCompletion(path, used, current);
                if (!ok) return {INF, {}};
                return {pathCost(path), path};
            }

            uniform_real_distribution<double> dist(0.0, total);
            double r = dist(rng);

            int chosen = cand.back().first;
            double acc = 0.0;
            for (auto &p : cand) {
                acc += p.second;
                if (acc >= r) {
                    chosen = p.first;
                    break;
                }
            }

            used[chosen] = 1;
            path.push_back(chosen);
            current = chosen;
        }

        if (cost[current][START] == -1) {
            // fallback greedy pentru închidere imposibilă direct
            return {INF, {}};
        }

        path.push_back(START);
        return {pathCost(path), path};
    };

    auto twoOptDirectedCycle = [&](vector<int> path) -> vector<int> {
        // Îmbunătățire locală ușoară. Pentru graf orientat incomplet trebuie
        // verificată existența tuturor arcelor după inversare.
        if (path.empty()) return path;

        bool improved = true;
        int limitPasses = 8;
        while (improved && limitPasses--) {
            improved = false;

            // path are forma [0, ..., 0]
            for (int i = 1; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    vector<int> cand = path;
                    reverse(cand.begin() + i, cand.begin() + j + 1);

                    long long oldCost = pathCost(path);
                    long long newCost = pathCost(cand);

                    if (newCost < oldCost) {
                        path.swap(cand);
                        improved = true;
                    }
                }
            }
        }
        return path;
    };

    int stagnation = 0;

    for (int epoch = 1; epoch <= EPOCHS; epoch++) {
        vector<pair<long long, vector<int>>> ants;
        ants.reserve(ANTS);

        long long epochBest = INF;
        vector<int> epochPath;

        for (int k = 0; k < ANTS; k++) {
            auto sol = constructAnt();
            if (sol.first < INF) {
                sol.second = twoOptDirectedCycle(sol.second);
                sol.first = pathCost(sol.second);
            }

            if (sol.first < epochBest) {
                epochBest = sol.first;
                epochPath = sol.second;
            }
            ants.push_back(sol);
        }

        // Evaporare
        for (int i = 0; i < N; i++) {
            for (auto &e : g[i]) {
                pher[i][e.to] *= (1.0 - EVAP);
                if (pher[i][e.to] < 1e-8) pher[i][e.to] = 1e-8;
            }
        }

        // Depunere de la cele mai bune soluții din epocă
        sort(ants.begin(), ants.end(), [](const auto& a, const auto& b) {
            return a.first < b.first;
        });

        int eliteCount = min(8, (int)ants.size());
        for (int idx = 0; idx < eliteCount; idx++) {
            if (ants[idx].first >= INF) continue;
            double delta = Q / (double)ants[idx].first;
            for (int i = 0; i + 1 < (int)ants[idx].second.size(); i++) {
                int u = ants[idx].second[i];
                int v = ants[idx].second[i + 1];
                pher[u][v] += delta;
            }
        }

        // Actualizare best global + elitist deposit
        if (epochBest < globalBest) {
            globalBest = epochBest;
            globalPath = epochPath;
            stagnation = 0;
        } else {
            stagnation++;
        }

        if (globalBest < INF) {
            double bonus = ELITIST * Q / (double)globalBest;
            for (int i = 0; i + 1 < (int)globalPath.size(); i++) {
                int u = globalPath[i];
                int v = globalPath[i + 1];
                pher[u][v] += bonus;
            }
        }

        // Anti-stagnation: reîmprospătare parțială a feromonilor
        if (stagnation == 1500) {
            for (int i = 0; i < N; i++) {
                for (auto &e : g[i]) {
                    pher[i][e.to] = 0.5 * pher[i][e.to] + 0.5;
                }
            }
        }

        // Restart mai agresiv dacă se blochează mult
        if (stagnation == 3500) {
            for (int i = 0; i < N; i++) {
                for (auto &e : g[i]) {
                    pher[i][e.to] = 1.0;
                }
            }
            stagnation = 0;
        }
    }

    if (globalBest == INF) cout << "Nu exista solutie\n";
    else cout << globalBest << "\n";

    return 0;
}