#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

void open(){
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
}
#define pb push_back
#define sz size()
#define MAXN 18
const int oo=(int)1e9;
vector<int>g[MAXN];
int n,m,cost[MAXN][MAXN],f[(1<<MAXN)][MAXN],ans,a,b,c;

int dp(int a,int b){
    if (a==(1<<n)-1) return 0;
    if (f[a][b]!=-1) return f[a][b];
    int res=oo;
    for (vector<int>::iterator it=g[b].begin();it!=g[b].end();it++){
        if ((a & (1<<*it))==0){
            if (res>cost[b][*it]){
                res=min(res,dp(a|(1<<*it),*it)+cost[b][*it]);
            }
        }
    }
    return f[a][b]=res;
}

int main(){
    open();
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            cost[i][j]=oo;
        }
    }
    for (int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        g[a].pb(b);
        cost[a][b]=min(cost[a][b],c);
    }
    ans=oo;
    memset(f,-1,sizeof(f));
    for (vector<int>::iterator it=g[0].begin();it!=g[0].end();it++){
        ans=min(ans,dp((1<<*it),*it)+cost[0][*it]);
    }
    printf("%d\n",ans);
    //system("pause");
    return 0;
}