#include<fstream>
#include<vector>
#define maxN 19
#define M (1<<30)
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
struct nod{
int inf,c;
};
vector<nod>v[maxN];
int n,m,mini=M,sol[maxN],s;
bool viz[maxN];
void citire()
{
    int i,x,y,z;
    nod a;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a.c=z;
        a.inf=y;v[x].push_back(a);

    }

}
int exista_muchie(int a,int b,int &s)
{
    for(int i=0;i<v[a].size();i++)
        if(v[a][i].inf==b)
            {
                s=v[a][i].c;
                return 1;
            }
    return 0;
}
void hamiltonian(int nod,int pas,int cost)
{
    viz[nod]=true;
    sol[pas]=nod;
    s+=cost;
    if(pas==n)
    {
        int costul;
        if(exista_muchie(sol[pas],0,costul))
           {
                s+=costul;
               mini=min(mini,s);
               s-=costul;
           }
    }
    else
        for(int i=0;i<v[nod].size();i++)
        {
            int vec = v[nod][i].inf;
            if(viz[vec]==false)
            {

               viz[vec]=true;
               hamiltonian(vec,pas+1,v[nod][i].c);

            }
        }
    s-=cost;
    sol[pas]=0;
    viz[nod]=false;
}
bool validare()
{
    for(int i=0;i<n;i++)
        if(v[i].size()<n/2)return false;
    return true;

}
int main()
{
    citire();
    if(validare()==false){
            g<<"Nu exista solutie";
            return 0;
    }
    hamiltonian(0,1,0);
    g<<mini<<'\n';
    return 0;
}