#include<iostream>
#include<vector>
using namespace std;
#define MOD 1000000007
#define NMAX 21
#define INF 0xfffffff
int n,m;
vector<vector<int>>dp;
vector<vector<pair<int,int>>>g;
#ifdef DEBUG
int to_idx(int x){
    int i=0;
    while((1<<i)!=x)++i;
    return i;
}
vector<bool>bits(int x){
    vector<bool>b;
    for(int i=n-1;i>=0;--i){
        b.push_back((1<<i)&x);
    }
    return b;
}
ostream&operator<<(ostream&out,vector<bool>b){
    for(const auto&i:b)out<<i;
    return out;
}
#endif
signed main(){
    #ifdef LOCAL
        freopen("date.in","r",stdin);
    #else
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        freopen("hamilton.in","r",stdin);
        freopen("hamilton.out","w",stdout);
    #endif
    cin>>n>>m;
    dp.assign(1<<n,vector<int>(n,INF));
    g.resize(n);
    for(int i=0;i<m;++i){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z});
    }
    dp[1][0]=0;
    for(int mask=0;mask<(1<<n);++mask){
        for(int i=0;i<n;++i){
            if(!(mask&(1<<i))||dp[mask][i]==INF)continue;
            for(const auto&e:g[i]){
                int j=e.first,z=e.second;
                if(!(mask&(1<<j))){
                    if(dp[mask|(1<<j)][j]>dp[mask][i]+z){
                        dp[mask|(1<<j)][j]=dp[mask][i]+z;
                    }
                }
            }
        }
    }
    // complete the cycle 
    int ans=INF;
    for(int i=0;i<n;++i){
        if(dp[(1<<n)-1][i]-INF){
            for(const auto&e:g[i]){
                if(!e.first){ // node 0
                    ans=min(ans,dp[(1<<n)-1][i]+e.second);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}