#include <cstdio>

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

const int Q=20,INF=1000000007;

int v[Q][Q];

int d[1<<18][Q];

int nod,muc;

int inline min(int a, int b)
{
    return a<b?a:b;
}

int main()
{
    fscanf(in,"%d%d",&nod,&muc);

    int a,b,c;

    for(int i=0; i<nod; i++)
    {
        for(int j=0; j<nod; j++)
            v[i][j]=INF;
    }

    for(int i=1; i<=muc; i++)
    {
        fscanf(in,"%d%d%d",&a,&b,&c);
        v[a][b]=c;
    }

    int p2=1<<nod;

    for(int i=0; i<p2; i++)
    {
        for(int j=0; j<nod; j++)
            d[i][j]=INF;
    }

    d[1][0]=0;

    for(int i=1; i<p2; i++)
    {
        for(int k=0; k<nod; k++)
        {
            if((i>>k)&1==1)
            {
                for(int t=0; t<nod; t++)
                {
                    if((i>>t)&1==1)
                        d[i][k]=min(d[i][k],(d[i^(1<<k)][t])+v[t][k]);
                }
            }
        }
    }

    int rez=INF;

    for(int k=0; k<nod; k++)
    {
        rez=min(rez,d[p2-1][k]+v[k][0]);
    }

    fprintf(out,"%d",rez);

    return 0;
}