#include <fstream>
using namespace std;
#define int long long
const int maxn=19;
const int maxl=(1<<18)+1;
int dp[maxl][maxn];
int cost[maxn][maxn];
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
void solve() {
    int n,m;
    cin>>n>>m;
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) {
            cost[i][j]=1e18;
            cost[j][i]=1e18;
        }
    }
    for (int i=0;i<m;i++) {
        int l,r,c;
        cin>>l>>r>>c;
        cost[l][r]=c;
        //cost[r][l]=c;
    }
    for (int i=0;i<(1<<n);i++) {
        for (int j=0;j<n;j++) {
            dp[i][j]=1e18;
        }
    }
    dp[1][0]=0;
    for (int i=1;i<(1<<n);i++) {
        for (int j=0;j<n;j++) {
            if (i&(1<<j)) {
                for (int k=0;k<n;k++) {
                    if (!(i&(1<<k))) {
                        dp[(i|(1<<k))][k]=min(dp[(i|(1<<k))][k],dp[i][j]+cost[j][k]);
                    }
                }
            }
        }
    }
    int mini=1e18;
    for (int i=0;i<n;i++) {
        mini=min(mini,dp[(1<<n)-1][i]+cost[i][0]);
    }
    cout<<mini<<endl;
}
signed main() {
    int t;
    t=1;
    while (t--)solve();
    return 0;
}