#include <fstream>
#define DMAX 20
#define INF 1999999999

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m;
int C[DMAX][DMAX];
int sol[DMAX], cost;
int solmin[DMAX], costmin;
bool uz[DMAX];

void citire();
void initializare();
void generare(int);
void schimbsol();
void afisare();

int main()
{
    citire();
    sol[1]=1; costmin=INF;
    generare(2);
    afisare();
    return 0;
}

void citire()
{
    int i, x, y, c;
    fin>>n>>m;
    initializare();
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        ++x; ++y;
        C[x][y]=c;
    }
}

void initializare()
{
    int i, j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            C[i][j]=INF;
        C[i][i]=0;
    }
}

void generare(int k)
{
    if(cost>costmin) return;

    if(k==n+1)
    {
        if(C[sol[n]][1]==INF) return;

        cost+=C[sol[n]][1];
        if(cost<costmin)
            schimbsol();

        cost-=C[sol[n]][1];
        return;
    }

    int i;
    for(i=2;i<=n;i++)
        if(!uz[i] && C[sol[k-1]][i]!=INF)
        {
            uz[i]=1; sol[k]=i;
            cost+=C[sol[k-1]][i];
            generare(k+1);
            cost-=C[sol[k-1]][i];
            uz[i]=0;
        }
}

void schimbsol()
{
    int i;
    for(i=1;i<=n;i++)
        solmin[i]=sol[i];
    costmin=cost;
}

void afisare()
{
    if(costmin==INF)
    {
        fout<<"Nu exista solutie\n";
        return;
    }
    fout<<costmin<<'\n';
}