#include<cstdio>
#define inf 1000000
#define NMax 20
using namespace std;

int H[1<<NMax][NMax];
int N,vc[NMax][NMax];

int hamilton (int i, int j)
{
    if (H[i][j]!=-1)
        return H[i][j];
    int min=inf,nod,aux;
    for (nod=0; nod<N; nod++)
        if (((1<<nod) & i) && vc[nod][j])
        {
            aux=hamilton(i^(1<<j),nod);
            if (aux+vc[nod][j]<min)
                min=aux+vc[nod][j];
        }
    H[i][j]=min;
    return min;
}

int main ()
{
    int min=inf,M,i,x,y,cst,j,rez;
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1; i<=M; i++)
    {
        scanf("%d%d%d",&x,&y,&cst);
        vc[x][y]=cst;
    }
    for (i=0; i<(1<<N); i++)
        for (j=0; j<N; j++)
            H[i][j]=-1;
    H[1][0]=0;
    for (i=1; i<N; i++)
        if (vc[i][0])
        {
            rez=hamilton((1<<N)-1,i);
            if (rez+vc[i][0]<min)
                min=rez+vc[i][0];
        }
    printf("%d\n",min);
    return 0;
}