#include <bits/stdc++.h>
#define INFILE "hamilton.in"
#define OUTFILE "hamilton.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
const int NMAX=30;
const int PMAX=262150;
const int INF=INT_MAX/2;
array<array<int,NMAX>,PMAX> C;//C[i][j]==drumul minim de la 0 la j continand bitii i de noduri
array<array<int,NMAX>,NMAX> Cost;
int N,M;
struct Graph{
    vector<vector<int>> Adj;
    void init(int n){
        Adj.resize(n+1);
    }
    void add(int x, int y){
        Adj[x].push_back(y);
    }
}G;

void Read(){
    in>>N>>M;
    G.init(N);
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            Cost[i][j]=INF;
        }
    }
    for(int i=1;i<=M;i++){
        int x,y,c;
        in>>x>>y>>c;
        G.add(y,x);
        Cost[x][y]=c;
    }
}

void Determinare(){
    for (int i = 0; i < 1 << N; ++i)
        for (int j = 0; j < N; ++j) C[i][j] = INF;
    C[1][0]=0;
    for(int i=0;i<(1<<N);i++){
        for(int j=0;j<N;j++){
            if(i&(1<<j)==0) continue;
            for(auto k:G.Adj[j]){
                if(i&(1<<k)==0) continue;
                C[i][j]=min(C[i][j],C[i^(1<<j)][k]+Cost[k][j]);
                //cout<<i<<" "<<j<<" "<<k<<"\n";
            }
        }
    }
    //cout<<"Da\n";
    int Min=INF;
    for(auto k:G.Adj[0]){
        Min=min(Min,C[(1<<N)-1][k]+Cost[k][0]);
    }
    out<<Min;
}

int main(){
    Read();
    Determinare();
    return 0;
}