/*
d[i][j]=costul minim al unui drum care pleaca din 0, se termina in j si trece exact o data prin varfurile date de i
d[i][j]=min{j' in i}( d[i xor (1<<j')][j'] + cost(j',j) )
=> min{j}( d[(1<<n)-1][j] + cost(j,0) as last edge )
*/
#include<fstream>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int Nmax = 19;
const int INF = (1<<30);
int C[Nmax][Nmax];
int D[(1<<Nmax)][Nmax];
int N,M;
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y,c;
        in>>x>>y>>c;
        C[x][y]=c;
    }
    for(int i=0;i<=(1<<(N))-1;i++){
        for(int j=0;j<N;j++){
            D[i][j]=INF;
        }
    }
    D[1][0]=0;
    for(int i=1;i<=(1<<(N))-1;i++){
        for(int j=0;j<N;j++){
            if( i&(1<<j) )
            for(int k=0;k<N;k++){
                if( (i&(1<<k)) && C[k][j] )
                    D[i][j]=min(D[i][j],( D[i^(1<<j)][k] + C[k][j] ));
            }
        }
    }
    int Ans=INF;
    for(int j=0;j<N;j++){
        if( C[j][0] )
            Ans=min(Ans,( D[(1<<(N))-1][j] + C[j][0] ));
    }
    out<<Ans<<'\n';
    return 0;
}