#include<fstream>
#include<iostream>
#include<vector>
#define inf 1e9
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector<vector<pair<int,int>>>revGraph;
const int NMAX1=18;
const int NMAX2=(1<<NMAX1)+1;
int dp[NMAX2][NMAX1];

void setUp(){
    for(int i=0;i<NMAX2;++i){
        for(int j=0;j<NMAX1;++j){
            dp[i][j]=inf;   
        }
    }
}
int main(){
    setUp();
    int n,m;
    fin>>n>>m;
    int u,v,cost;
    revGraph.resize(n+1);
    for(int i=0;i<m;++i){
        fin>>u>>v>>cost;
        revGraph[v].push_back(make_pair(u,cost));
    }
    dp[1][0]=0;
    for(int mask=1;mask< (1 << n);++mask){
        for(int i=0;i<n;++i){
            if(mask&(1<<i)){ 
                for(auto vecin:revGraph[i]){
                    int vec=vecin.first;
                    int cost=vecin.second;
                    dp[mask][i]=min(dp[mask][i],dp[mask-(1<<i)][vec]+cost);
                }
            }
        }
    }
    int fullMax=(1<<n)-1;//contine n elemente
    int rez=inf;
    for(auto i:revGraph[0]){
        rez=min(rez,dp[fullMax][i.first]+ i.second);
    }
    fout<<rez;
    return 0;
}