#include <bits/stdc++.h>

using namespace std;

const int NMAX = 19;
const int ants = 128;
const double Q = 100;
const double evaporation = 6;

int cost[NMAX][NMAX];
double pb[NMAX][NMAX];
vector <int> nodes[NMAX];
vector <int> newNodes[NMAX];
int best = 2e9;

struct Ant {
    vector <int> drum;
    int total;
    int viz;
    void Antt() {
        total = viz = 0;
        drum.clear();
    }
    void add(int node, int cst) {
        drum.push_back(node);
        total += cst;
        viz |= (1 << (node - 1));
    }
    void augment(){
        if(cost[drum.back()][drum[0]] == 0) return;
        total += cost[drum.back()][drum[0]];
        best = min(best, total);
        //cout << "DRUM DE " <<  total << "\n";
        while(drum.size() > 1){
            int last = drum.back();
                     //   cout << last << " ";

            drum.pop_back();
            pb[drum.back()][last] += Q / total;
        }
       // cout << drum.back() << "\n\n\n";
    }
    bool contains(int node){
        return (viz & (1 << (node - 1)));
    }
} ant[10001];

int main() {
    ifstream cin(".in");
    ofstream cout(".out");
    int n, m, i, j;
    srand(time(0));
    cin >> n >> m;
    for(i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a++;
        b++;
        cost[a][b] = c;
        pb[a][b] = evaporation;
    }
    for(int iteration = 0; iteration < 200; iteration++) {
        for(i = 1; i <= n; i++) {
            nodes[i].clear();
            newNodes[i].clear();
            for(j = 1; j <= n; j++) pb[i][j] = pb[i][j] / evaporation;
        }
        int c = 0;
        for(i = 1; i <= n; i++) {
            for(int j = 1; j <= ants; j++) {
                newNodes[i].push_back(++c);
                ant[c].Antt();
                ant[c].add(i, 0);
            }
        }
        for(int step = 1; step < n; step++) {
            for(i = 1; i <= n; i++){
                swap(newNodes[i], nodes[i]);
                newNodes[i].clear();
            }
            for(int i = 1; i <= n; i++) {
                for(auto x : nodes[i]) {
                    double r = ((double) rand() / (RAND_MAX));
                    double s = 0;
                    for(int j = 1; j <= n; j++) {
                        if(cost[i][j] != 0 && !ant[x].contains(j)) {
                            s += pb[i][j];
                        }
                    }
                    for(int j = 1; j <= n; j++) {
                        if(cost[i][j] != 0 && !ant[x].contains(j)) {
                            r -= pb[i][j] / s;
                            if(r < 0) {
                                newNodes[j].push_back(x);
                                ant[x].add(j, cost[i][j]);
                            }
                        }
                    }
                }
            }
        }
        for(i = 1; i <= n; i++) {
            for(auto x : newNodes[i]) {
                ant[x].augment();
            }
        }
    }
    cout << best;
    return 0;
}