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

static const int MAXN = 18;
static const int INF = 1000000000;

int N, M;
int costm[MAXN][MAXN];
double tauPher[MAXN][MAXN];
double desir[MAXN][MAXN];
double invCost[MAXN][MAXN];

int outdegv[MAXN], indegv[MAXN];

int bestCost = INF;
int bestPath[MAXN + 1];

static uint64_t seed64 = 1469598103934665603ull;

static inline uint64_t xrng() {
    seed64 ^= seed64 << 7;
    seed64 ^= seed64 >> 9;
    return seed64;
}

static inline double rnd01() {
    return (xrng() >> 11) * (1.0 / 9007199254740992.0);
}

static inline int rndInt(int lim) {
    return (int)(xrng() % (uint64_t)lim);
}

bool greedyInit(int start, int path[MAXN + 1], int &cst) {
    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 bestEdge = INF;
        for (int v = 0; v < N; v++) {
            if ((used >> v) & 1u) continue;
            int w = costm[cur][v];
            if (w == -1) continue;
            if (w < bestEdge) {
                bestEdge = w;
                nxt = v;
            }
        }
        if (nxt == -1) return false;
        path[step] = nxt;
        used |= (1u << nxt);
        total += costm[cur][nxt];
        cur = nxt;
    }

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

inline void rebuildDesir() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (costm[i][j] == -1) desir[i][j] = 0.0;
            else desir[i][j] = tauPher[i][j] * invCost[i][j];
        }
    }
}

bool buildAnt(int start, int path[MAXN + 1], int &cst, double q0) {
    unsigned used = 0;
    used |= (1u << start);
    path[0] = start;
    int cur = start;
    int total = 0;

    for (int step = 1; step < N; step++) {
        int cand[MAXN];
        double score[MAXN];
        int cnt = 0;

        int bestNode = -1;
        double bestScore = -1.0;
        double sum = 0.0;

        for (int v = 0; v < N; v++) {
            if ((used >> v) & 1u) continue;
            if (costm[cur][v] == -1) continue;

            double sc = desir[cur][v];
            cand[cnt] = v;
            score[cnt] = sc;
            cnt++;

            sum += sc;
            if (sc > bestScore) {
                bestScore = sc;
                bestNode = v;
            }
        }

        if (cnt == 0) return false;

        int nxt;
        if (rnd01() < q0) {
            nxt = bestNode;
        } else if (sum <= 0.0) {
            nxt = cand[rndInt(cnt)];
        } else {
            double r = rnd01() * sum;
            double acc = 0.0;
            nxt = cand[cnt - 1];
            for (int i = 0; i < cnt; i++) {
                acc += score[i];
                if (acc >= r) {
                    nxt = cand[i];
                    break;
                }
            }
        }

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

    if (costm[cur][start] == -1) return false;
    total += costm[cur][start];
    path[N] = start;
    cst = 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++) {
        outdegv[i] = indegv[i] = 0;
        for (int j = 0; j < N; j++) {
            costm[i][j] = -1;
        }
    }

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

    if (N == 1) {
        // conform restricțiilor nu există arc la sine însuși
        cout << "Nu exista solutie\n";
        return 0;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (costm[i][j] != -1) {
                outdegv[i]++;
                indegv[j]++;
            }
        }
    }

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

    const int START = 0;

    // Parametri intenționat mici ca să nu explodeze timpul
    const int ANTS = 20;
    const int EPOCHS = 1000;
    const double EVAP = 0.22;
    const double Q0 = 0.96;
    const double ELITE = 1.8;

    int initPath[MAXN + 1], initCost;
    double tau0 = 1e-4;

    if (greedyInit(START, initPath, initCost)) {
        bestCost = initCost;
        for (int i = 0; i <= N; i++) bestPath[i] = initPath[i];
        tau0 = 1.0 / (double)initCost;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (costm[i][j] == -1) {
                tauPher[i][j] = 0.0;
                invCost[i][j] = 0.0;
            } else {
                tauPher[i][j] = tau0;
                invCost[i][j] = 1.0 / (double)costm[i][j];
            }
        }
    }
    rebuildDesir();

    int antPath[MAXN + 1];
    int iterBestPath[MAXN + 1];
    int stagnation = 0;

    for (int epoch = 0; epoch < EPOCHS; epoch++) {
        int iterBestCost = INF;
        bool found = false;

        for (int k = 0; k < ANTS; k++) {
            int curCost;
            if (buildAnt(START, antPath, curCost, Q0)) {
                if (curCost < iterBestCost) {
                    iterBestCost = curCost;
                    found = true;
                    for (int i = 0; i <= N; i++) iterBestPath[i] = antPath[i];
                }
            }
        }

        // evaporare pe toată matricea - doar 18x18, e ieftină
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (costm[i][j] != -1) {
                    tauPher[i][j] *= (1.0 - EVAP);
                    if (tauPher[i][j] < 1e-12) tauPher[i][j] = 1e-12;
                }
            }
        }

        if (found) {
            double d1 = 1.0 / (double)iterBestCost;
            for (int i = 0; i < N; i++) {
                int u = iterBestPath[i];
                int v = iterBestPath[i + 1];
                tauPher[u][v] += d1;
            }

            if (iterBestCost < bestCost) {
                bestCost = iterBestCost;
                for (int i = 0; i <= N; i++) bestPath[i] = iterBestPath[i];
                stagnation = 0;
            } else {
                stagnation++;
            }
        } else {
            stagnation++;
        }

        if (bestCost < INF) {
            double d2 = ELITE / (double)bestCost;
            for (int i = 0; i < N; i++) {
                int u = bestPath[i];
                int v = bestPath[i + 1];
                tauPher[u][v] += d2;
            }
        }

        if (stagnation >= 40) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (costm[i][j] != -1) tauPher[i][j] = tau0;
                }
            }
            stagnation = 0;
        }

        rebuildDesir();
    }

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

    return 0;
}