#include <bits/stdc++.h>
#define MAX 20
#define mp make_pair
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
typedef pair <int, int> pairINT;

int n,m,ans,dp[(1<<MAX)][MAX];
bool used[MAX];
vector <pairINT> tg[MAX*MAX];

void read();
void solve();
void calcans();

int main(){
    read();
    solve();
    calcans();
    fout<<ans;
    return 0;
}
void read(){
    int i,x,y,c;
    fin>>n>>m;
    for(i=0;i<m;++i){
        fin>>x>>y>>c;
        tg[y].push_back(mp (x,c));
    }
}
void solve(){
    int i,config,poz,nod;

    dp[1][0]=0;

    for(i=2;i<(1<<n);++i){
        config=i;
        poz=0;
        while(config){
            if(config%2){
                used[poz]=1;
                dp[i][poz]=(int)(1e9);
            }
            ++poz;
            config/=2;
        }
        config=i;
        poz=0;
        while(config){
            if(config%2){
                nod=poz;

                if(i == (1<<poz))
                    break;

                for(auto it:tg[nod]){
                    if(used[it.first]){
                        dp[i][nod]=min(dp[i][nod],dp[i-(1<<poz)][it.first] + it.second);
                    }
                }
            }

            ++poz;
            config/=2;
        }
        memset(used,0,sizeof(used));
    }
}
void calcans(){
    ans=(int)(1e9);
    for(auto it:tg[0])
        ans=min(ans, dp[(1<<n)-1][it.first] + it.second);
}