#include <bits/stdc++.h>
#define int long long
using namespace std;

ifstream fin("podm.in");
ofstream fout("podm.out");

const int dim=500009,inf=1e18;

int n,m,cost[20][20];
int memo[dim][20];

int dp(int stare,int last){
    if(memo[stare][last]==-1){
        int ans=inf;
        for(int i=0;i<n;i++){
            if(cost[i][last] && stare&(1<<i)){
                int stare_noua=stare^(1<<last);
                ans=min(ans,dp(stare_noua,i)+cost[i][last]);
            }
        }
        memo[stare][last]=ans;
    }
    return memo[stare][last];
}

signed main(){
        fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        cost[x][y]=c;
    }
    for(int i=0;i<=(1<<n);i++){
        for(int j=0;j<n;j++){
            memo[i][j]=-1;
        }
    }
    memo[1][0]=0;
    int ans=inf;
    for(int i=0;i<n;i++){
        if(cost[i][0]){
            ans=min(ans,dp((1<<n)-1,i)+cost[i][0]);
        }
    }
        fout<<ans;
}