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

static const int MAXN = 18;
static const int INF = 1e9;

int N, M;
int w[MAXN][MAXN];
double tauPher[MAXN][MAXN];
double etaPow[MAXN][MAXN];

int candList[MAXN][MAXN];
int candCnt[MAXN];

int bestGlobalCost = INF;
int bestGlobalPath[MAXN + 1];

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

inline double fastRand01() {
    static uniform_real_distribution<double> dist(0.0, 1.0);
    return dist(rng);
}

inline int bitCount(unsigned x) {
    return __builtin_popcount(x);
}

bool greedyInit(int start, int path[], int &costOut) {
    unsigned used = 0;
    used |= (1u << start);
    path[0] = start;
    int cur = start;
    int total = 0;

    for (int step = 1; step < N; step++) {
        int nxt = -1;
        int bestC = INF;
        for (int v = 0; v < N; v++) {
            if ((used >> v) & 1u) continue;
            if (w[cur][v] == -1) continue;
            if (w[cur][v] < bestC) {
                bestC = w[cur][v];
                nxt = v;
            }
        }
        if (nxt == -1) return false;
        path[step] = nxt;
        used |= (1u << nxt);
        total += w[cur][nxt];
        cur = nxt;
    }

    if (w[cur][start] == -1) return false;
    path[N] = start;
    total += w[cur][start];
    costOut = total;
    return true;
}

void buildCandidateLists() {
    for (int u = 0; u < N; u++) {
        vector<pair<int,int>> vec;
        vec.reserve(N);
        for (int v = 0; v < N; v++) {
            if (u == v) continue;
            if (w[u][v] != -1) vec.push_back({w[u][v], v});
        }
        sort(vec.begin(), vec.end());
        candCnt[u] = 0;
        int lim = min((int)vec.size(), 8); // candidate list mică și rapidă
        for (int i = 0; i < lim; i++) {
            candList[u][candCnt[u]++] = vec[i].second;
        }
    }
}

inline int chooseNextACS(int cur, unsigned used, double alpha, double betaDummy, double q0) {
    int bestNode = -1;
    double bestScore = -1.0;

    // 1) încercăm întâi candidate list
    int availCnt = 0;
    int availNodes[MAXN];
    double availScores[MAXN];
    double sum = 0.0;

    for (int i = 0; i < candCnt[cur]; i++) {
        int v = candList[cur][i];
        if ((used >> v) & 1u) continue;
        double score = pow(tauPher[cur][v], alpha) * etaPow[cur][v];
        availNodes[availCnt] = v;
        availScores[availCnt] = score;
        sum += score;
        if (score > bestScore) {
            bestScore = score;
            bestNode = v;
        }
        availCnt++;
    }

    // 2) fallback pe toate muchiile dacă lista scurtă nu conține nimic utilizabil
    if (availCnt == 0) {
        sum = 0.0;
        bestScore = -1.0;
        for (int v = 0; v < N; v++) {
            if ((used >> v) & 1u) continue;
            if (w[cur][v] == -1) continue;
            double score = pow(tauPher[cur][v], alpha) * etaPow[cur][v];
            availNodes[availCnt] = v;
            availScores[availCnt] = score;
            sum += score;
            if (score > bestScore) {
                bestScore = score;
                bestNode = v;
            }
            availCnt++;
        }
    }

    if (availCnt == 0) return -1;

    // ACS: cu probabilitatea q0 alegem best determinist
    if (fastRand01() < q0) return bestNode;

    // altfel roulette
    if (sum <= 0.0) return availNodes[uniform_int_distribution<int>(0, availCnt - 1)(rng)];

    double r = fastRand01() * sum;
    double acc = 0.0;
    for (int i = 0; i < availCnt; i++) {
        acc += availScores[i];
        if (acc >= r) return availNodes[i];
    }
    return availNodes[availCnt - 1];
}

bool constructAntACS(
    int start,
    int path[],
    int &costOut,
    double alpha,
    double beta,
    double q0,
    double localEvap,
    double tau0
) {
    (void)beta; // etaPow e deja pre-ridicat la puterea beta

    unsigned used = 0;
    used |= (1u << start);
    path[0] = start;
    int cur = start;
    int total = 0;

    for (int step = 1; step < N; step++) {
        int nxt = chooseNextACS(cur, used, alpha, beta, q0);
        if (nxt == -1) return false;

        total += w[cur][nxt];
        path[step] = nxt;
        used |= (1u << nxt);

        // local pheromone update (ACS)
        tauPher[cur][nxt] = (1.0 - localEvap) * tauPher[cur][nxt] + localEvap * tau0;

        cur = nxt;
    }

    if (w[cur][start] == -1) return false;
    total += w[cur][start];
    path[N] = start;

    tauPher[cur][start] = (1.0 - localEvap) * tauPher[cur][start] + localEvap * tau0;

    costOut = total;
    return true;
}

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

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

    cin >> N >> M;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            w[i][j] = -1;

    vector<int> indeg(N, 0), outdeg(N, 0);

    for (int i = 0; i < M; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        if (w[x][y] == -1 || c < w[x][y]) w[x][y] = c;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (w[i][j] != -1) {
                outdeg[i]++;
                indeg[j]++;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        if (indeg[i] == 0 || outdeg[i] == 0) {
            cout << "Nu exista solutie\n";
            return 0;
        }
    }

    if (N == 1) {
        if (w[0][0] == -1) cout << "Nu exista solutie\n";
        else cout << w[0][0] << "\n";
        return 0;
    }

    const int START = 0;

    // Parametri rapizi și mai conservatori
    const int ANTS = 24;
    const double alpha = 1.0;
    const double beta = 4.0;
    const double rho = 0.10;        // global evaporation
    const double localEvap = 0.08;  // local ACS update
    const double q0 = 0.88;         // mai mult exploit, mai puțin zgomot

    // Heuristică precomputată
    double greedyCostSeed = 0.0;
    {
        int p[MAXN + 1], cst;
        bool ok = greedyInit(START, p, cst);
        if (ok) {
            greedyCostSeed = cst;
            bestGlobalCost = cst;
            for (int i = 0; i <= N; i++) bestGlobalPath[i] = p[i];
        } else {
            // fallback generic
            greedyCostSeed = 1000.0;
        }
    }

    double tau0 = 1.0 / greedyCostSeed;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (w[i][j] == -1) {
                tauPher[i][j] = 0.0;
                etaPow[i][j] = 0.0;
            } else {
                tauPher[i][j] = tau0;
                etaPow[i][j] = pow(1.0 / (double)w[i][j], beta);
            }
        }
    }

    buildCandidateLists();

    int antPath[MAXN + 1];
    int iterBestPath[MAXN + 1];

    clock_t t0 = clock();

    // buget CPU aproximativ; poți ajusta dacă vrei
    while ((double)(clock() - t0) / CLOCKS_PER_SEC < 1.7) {
        int iterBestCost = INF;
        bool foundThisIter = false;

        for (int k = 0; k < ANTS; k++) {
            int cst;
            if (constructAntACS(START, antPath, cst, alpha, beta, q0, localEvap, tau0)) {
                if (cst < iterBestCost) {
                    iterBestCost = cst;
                    foundThisIter = true;
                    for (int i = 0; i <= N; i++) iterBestPath[i] = antPath[i];
                }
            }
        }

        // evaporare globală
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (w[i][j] != -1) {
                    tauPher[i][j] *= (1.0 - rho);
                    if (tauPher[i][j] < 1e-12) tauPher[i][j] = 1e-12;
                }
            }
        }

        // update best global
        if (foundThisIter && iterBestCost < bestGlobalCost) {
            bestGlobalCost = iterBestCost;
            for (int i = 0; i <= N; i++) bestGlobalPath[i] = iterBestPath[i];
        }

        // depunere doar pe best global
        if (bestGlobalCost < INF) {
            double delta = 1.0 / (double)bestGlobalCost;
            for (int i = 0; i < N; i++) {
                int u = bestGlobalPath[i];
                int v = bestGlobalPath[i + 1];
                tauPher[u][v] += delta;
            }
        }
    }

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

    return 0;
}