#include <bits/stdc++.h>
using namespace std;
vector<int> GT[18];
const int inf=1e9;
int dist[18][18],dp[(1<<18)][18];
int main(){
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            dist[i][j]=inf;
    for(int i=1;i<=m;++i){
        int from,to,cost;
        scanf("%d %d %d",&from,&to,&cost);
        GT[to].push_back(from);
        dist[from][to]=cost;
    }
    int MAX_BITS=(1<<n)-1;
    for(int i=0;i<n;++i)
        if(i==0)
            dp[1][i]=0;
        else dp[1][i]=inf;
    for(int i=2;i<=MAX_BITS;++i)
        for(int j=0;j<n;++j){
            dp[i][j]=inf;
            for(auto it :GT[j])
                if(i&(1<<it))
                    dp[i][j]=min(dp[i][j],dp[i^(1<<it)][it]+dist[it][j]);
        }
    int sol=inf;
    for(int i=1;i<n;++i)
        sol=min(sol,dp[MAX_BITS][i]+dist[i][0]);
    printf("%d\n",sol);
    return 0;
}