#include <stdio.h>

int e,n,i,j,min=18000000,d[262144][307],v[3][400];

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&n,&e);
    for (i=1;i<=e;++i)
        scanf("%d%d%d",&v[0][i],&v[1][i],&v[2][i]);
    for (i=1;i<=e;++i)
        if (!v[0][i])
            d[1+(1<<v[1][i])][v[1][i]]=v[2][i];
    for (i=1;i<(1<<n)-1;i+=2)
        for (j=1;j<=e;++j)
            if ((v[0][j])&&(d[i][v[0][j]])&&(v[1][j])&&((i/(1<<v[1][j]))%2==0)&&((!d[i+(1<<v[1][j])][v[1][j]])||(d[i+(1<<v[1][j])][v[1][j]]>d[i][v[0][j]]+v[2][j])))
            {
                d[i+(1<<v[1][j])][v[1][j]]=d[i][v[0][j]]+v[2][j];
            }
    for (i=1;i<=e;++i)
        if ((!v[1][i])&&(min>d[(1<<n)-1][v[0][i]]+v[2][i]))
            min=d[(1<<n)-1][v[0][i]]+v[2][i];
    printf("%d",min);
    return 0;
}