#include <stdio.h>

using namespace std;

const int N = 20;
const int M = 400;
const int P = 1 << 19;
const int MAX = 20000000;

int cost[N][N];
int d[P][N];

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

    int n,m,i,j,k,x,y,c,minim;
    fscanf(in,"%d%d",&n,&m);

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            cost[i][j]=MAX;

    for(i=0;i<m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        cost[x][y]=c;
    }

    for(i=1;i<(1<<n);i+=2)
        for(j=0;j<n;j++)
            d[i][j]=MAX;

    d[1][0]=0;
    for(i=1;i<(1<<n);i+=2)
        for(j=1;j<n;j++)
        {
            if(!(i&(1<<j)))
                continue;
            minim=MAX;
            for(k=0;k<n;k++)
                if((i&(1<<k)) && k!=j)
                    if(minim > cost[k][j]+d[i^(1<<j)][k])
                        minim = cost[k][j]+d[i^(1<<j)][k];
            d[i][j]=minim;
        }
    minim=MAX;
    for(i=1;i<n;i++)
        if(minim > cost[i][0]+d[(1<<n)-1][i])
            minim = cost[i][0]+d[(1<<n)-1][i];
    fprintf(out,"%d",minim);
    return 0;
}