#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int INF=2000000;

int v[20][20];
int d[1<<19][20];

int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    int n,m,x,y,c,stare2;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i){
        scanf("%d %d %d",&x,&y,&c);
        v[x][y]=c;
    }
    for(int i=0;i<=19;++i)
        for(int j=0;j<=19;++j)
            if(v[i][j]==0)
                v[i][j]=INF;
    for(int i=1;i<(1<<19);++i)
        for(int j=0;j<=n;++j)
            d[i][j]=INF;
    d[1][0]=0;
    for(int stare=3;stare<=(1<<n);stare+=2){
        for(int j=1;j<n;++j){
            if((1<<j)&stare){
                stare2=(stare-(1<<j));
                for(int k=0;k<n;++k){
                    if(((1<<k)&stare2)&&d[stare2][k]+v[k][j]<d[stare][j]){
                        d[stare][j]=d[stare2][k]+v[k][j];
                    }
                }
            }
        }
    }
    int r=20000000;
    for(int i=1;i<n;++i){
        r=min(r,d[(1<<n)-1][i]+v[i][0]);
    }
    printf("%d\n",r);
    return 0;
}