#include <bits/stdc++.h>
#define bug(a) std::cerr << "(" << #a << ": " << a << ")\n";
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
const int inf=2e7;
const int T=3e6;
//fumez cocaina pentru cei care sunt interesati de solutie
//daca o intelegi tu ce fumezi?
int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    int n,m;
    cin>>n>>m;
    if(n==1)
    {
        cout<<0;
        return 0;
    }
    uniform_int_distribution<int> ui(0,n-1);
    uniform_real_distribution<double> uf(0.0f,1.0f);
    vector<vector<int>>cost(n,vector<int>(n,inf));
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        cost[x][y]=z;
    }
    vector<int>v(n);
    iota(all(v),0);
    int sol,acm,x,y;
    auto calculate=[&](const vector<int>&x)
    {
        int rez=0;
        for(int i=1;i<n;i++)
        {
            rez+=cost[x[i-1]][x[i]];
        }
        rez+=cost[x[n-1]][x[0]];
        return rez;
    };
    auto modify=[&]()
    {
        x=ui(mt);
        y=x;
        while(y==x)
        {
            y=ui(mt);
        }
    };
    sol=acm=calculate(v);
    for(int i=T;i;i--)
    {
        double time=(1.0f*i)/T;
        modify();
        auto aux=v;
        swap(aux[x],aux[y]);
        int newc=calculate(aux);
        sol=min(sol,newc);
        if(newc<acm || exp((double)(newc-acm)/time)>=uf(mt))
        {
            acm=newc;
            v=aux;
        }
    }
    cout<<sol;

}