#include <stdio.h>

using namespace std;

#define ll long long
#define INF 100000000

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

ll a[20][20];
ll c[300000][20];

int main()
{
    ll n,m,x,y,z,i,j,mn,v;
    fscanf(f,"%lld%lld",&n,&m);
    for (i=0;i<=n;i++) for (j=0;j<=n;j++) a[i][j]=INF;
    for (i=1;i<=m;i++){
        fscanf(f,"%lld%lld%lld",&x,&y,&z);
        a[x][y]=z;
    }
    for (i=0;i<1<<n;i++)
        for (j=0;j<n;j++) c[i][j]=INF;
    c[1][0]=0;
    m=(1<<n)-1;
    for (i=0;i<=m;i++)
        for (j=0;j<n;j++)
            if (i&(1<<j)){
                for (v=0;v<n;v++)
                    if (a[v][j]!=INF)
                        if (c[i^(1<<j)][v]+a[v][j]<c[i][j]) c[i][j]=c[i^(1<<j)][v]+a[v][j];
            }
    mn=INF;
    for (i=1;i<n;i++)
        if (a[i][0]!=INF&&mn>c[m][i]+a[i][0]) mn=c[m][i]+a[i][0];
    fprintf(g,"%lld",mn);
    fclose(f);
    fclose(g);
    return 0;
}