#include <fstream>
#include <vector>
using namespace std;
ifstream f ("traseu.in");
ofstream g ("traseu.out");
const int nmax=63;
vector <int> v[nmax];
vector <int> cost[nmax];
vector <int> val[nmax];
int n,m,a,b,c,usu,sol,viz[nmax*nmax],k;
void solve(int nod,int st,int ramas,int cst)
{
    if(nod==st&&ramas==0)
    {
        sol=min(sol,cst);
        return;
    }
    for(int i=0;i<v[nod].size();++i)
    {
        if(viz[val[nod][i]]<2)
        {
            ++viz[val[nod][i]];
            if(viz[val[nod][i]]==1) --ramas;
            solve(v[nod][i],st,ramas,cst+cost[nod][i]);
            --viz[val[nod][i]];
            if(viz[val[nod][i]]==0) ++ramas;
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>a>>b>>c;
        v[a].push_back(b);
        cost[a].push_back(c);
        val[a].push_back(++k);
    }
    sol=1e9;
    for(int i=1;i<=n;++i) solve(i,i,k,0);
    g<<sol;
    return 0;
}