#include <fstream>
#define NMAX 20
#define INFINIT 1000005
#define COSTINF 1000005*18
using namespace std;

ofstream fout("hamilton.out");

int n, m, C[NMAX][NMAX];
int sol[NMAX], solmin[NMAX], cost, costmin=COSTINF;
bool uz[NMAX];

void citire();
void perm(int);
bool OK(int);

int main()
{
    citire();
    sol[1]=1;
    uz[1]=true;
    perm(2);
    if(costmin==COSTINF)    fout<<"Nu exista solutie\n";
    else                    fout<<costmin<<'\n';
    return 0;
}

void citire()
{

    ifstream fin("hamilton.in");
    int i, j, x, y, c;
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        ++x, ++y;
        C[x][y]=c;
    }

    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            if(i!=j && !C[i][j])
                C[i][j]=INFINIT;
}

void perm(int k)
{
// sunt ocupate pozitile de la 1 la k-1
    int i;
    if(cost>costmin) return;
    if(k==n+1)
    {
        if(C[ sol[n] ][ sol[1] ]==INFINIT)
            return;
        cost+=C[sol[n]][1];
        if(cost<=costmin)
        {
            costmin=cost;
            for(i=1;i<=n;++i)
                solmin[i]=sol[i];
        }
        cost-=C[sol[n]][1];
        return;
    }
    for(i=2;i<=n;++i)
    {
        if(!uz[i] && C[ sol[k-1] ][ i ]!=INFINIT)
        {
            sol[k]=i;
            cost+=C[sol[k-1]][i];
            uz[i]=true;
            perm(k+1);
            cost-=C[sol[k-1]][i];
            uz[i]=false;
        }

    }
}