#include <fstream>
#define NMAX 20
#define INF 1000000000
using namespace std;

FILE * fin=fopen("hamilton.in", "r");
FILE * fout=fopen("hamilton.out", "w");

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

void citire();
void bkt(int k);
void afisare();

int main()
{
    citire();
    sol[1]=1;
    costmin=INF;

    bkt(2);
    afisare();

    return 0;
}

void citire()
{
    int i,j,x,y,cost;
    fscanf(fin,"%d%d",&n,&m);

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

    for(i=1;i<=m;i++)
    {

        fscanf(fin,"%d%d%d",&x,&y,&cost);
        ++x;++y;

        C[x][y]=cost;
    }
}

void bkt(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)
        {
            for(int i=1; i<=n; i++)
                solmin[i]=sol[i];
            costmin=cost;
        }
        cost-=C[sol[n]][1];
        return;
    }

    for(int 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];

            bkt(k+1);

            cost-=C[sol[k-1]][i];
            uz[i]=0;
        }
}

void afisare()
{
    if(costmin==INF)
    {
        fprintf(fout, "Nu exista solutie\n");
        return;
    }
    fprintf(fout, "%d", costmin);
}