#include<stdio.h>
#define MAX 999999999
#define N 18
#define M N*N
int x[M],v[M],prev[M],last[M],d[1<<N][N];
int main()
{
    FILE *fin,*fout;
    fin=fopen("hamilton.in","r");
    fout=fopen("hamilton.out","w");
    int n,m;
    fscanf(fin,"%d%d",&n,&m);
    int i,j;
    for(i=1; i<=m; i++){
        int y;
        fscanf(fin,"%d%d%d",&x[i],&y,&v[i]);
        prev[i]=last[y];
        last[y]=i;
    }
    int lim=1<<n;
    for(i=0; i<lim; i++)
        for(j=0; j<n; j++)
            d[i][j]=MAX;
    d[1][0]=0;
    for(i=0; i<lim; i++)
        for(j=0; j<n; j++)
            if(i&(1<<j)){
                int p=last[j];
                while(p!=0){
                    if(((i&(1<<j))!=0)&&(d[i][j]>d[i^(1<<j)][x[p]]+v[p]))
                        d[i][j]=d[i^(1<<j)][x[p]]+v[p];
                    p=prev[p];
                }
            }
    int min=MAX,p=last[0];
    while(p!=0){
        if(min>d[(1<<n)-1][x[p]]+v[p])
            min=d[(1<<n)-1][x[p]]+v[p];
        p=prev[p];
    }
    fprintf(fout,"%d",min);
    return 0;
}