#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(), (a).end()
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pb push_back
#define er erase
#define in insert
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
///#define cin fin
///#define cout fout
using namespace std;


//ofstream fout("file.out");

const int nmax=1e3+5;
const int mod=1e9+7;
const int mod1=998244353;

long long inv(long long a, long long b){
    return 1<a ? b - inv(b%a,a)*b/a : 1;
}

#define inf 100000000

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

int n,m,x,y,z,ans=inf,dp[20][700000],cost[23][23];
vector<int>nod[20];

int32_t main(){
//    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    fin >> n >> m;
    for(int i=1;i<=m;i++){
        fin >> x >> y >> z;
        nod[x].push_back(y);
        cost[x][y]=z;
    }
    for(int i=1;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            dp[j][i]=inf;
        }
    }
    dp[0][1]=0;
    for(int i=1;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if((1<<j)&i){
                for(int k=0;k<nod[j].size();k++){
                    int t=nod[j][k];
                    if(((1<<t)&i)==0 ){
                        dp[t][i+(1<<t)]=min(dp[t][i+(1<<t)],dp[j][i]+cost[j][t]);
                    }
                }
            }
        }
    }
    for(int j=0;j<nod[0].size();j++){
        if(cost[nod[0][j]][0])ans=min(ans,dp[nod[0][j]][(1<<n)-1]+cost[nod[0][j]][0]);
    }
    cout << ans << '\n';
}