#include<cstdio>
#include<vector>
#define inf 2000000000
using namespace std;
vector<pair<int,int> > g[20];
int dp[300000][20];
int minim(int a,int b){
    if(a>b)
        return b;
    return a;
}
int main(){
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    int n,m,i,j,k,a,b,c,dim,answer;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        g[b].push_back(make_pair(a,c));
    }
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            dp[i][j]=inf;
    dp[1][0]=0;
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++){
            if((i&(1<<j))==0)
                continue;
            dim=g[j].size();
            for(k=0;k<dim;k++){
                if((i&(1<<g[j][k].first))==0)
                    continue;
                dp[i][j]=minim(dp[i][j],dp[i-(1<<j)][g[j][k].first]+g[j][k].second);
            }
        }
    answer=2000000000;
    dim=g[0].size();
    for(i=0;i<dim;i++)
        answer=minim(answer,dp[(1<<n)-1][g[0][i].first]+g[0][i].second);
    printf("%d",answer);
    return 0;
}