#include<fstream>
#include<cstring>
#define DIM 18
#define INF 0x3f3f3f3f
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int D[1<<DIM][DIM],C[DIM][DIM],n,m,x,y,z;
int H( int conf ,int i ){
    if( conf == 0 ){
        return INF;
    }
    if( D[conf][i] != INF  ){
        return D[conf][i];
    }else{
        int conf1 = conf - (1<<i);
        for( int j = 0; j < n ; j++ ){
            if( ( conf1 >> j ) & 1 == 1 ){
                D[conf][i] = min( D[conf][i] ,H(conf1,j) + C[j][i] );
            }
        }
        return D[conf][i];
    }
}
int main(){
    fin >> n >> m;
        memset(C,INF,sizeof(C));
    for( int i = 1 ; i <= m ; i++ ){
        fin >> x >> y >> z;
        C[x][y] = z;
    }
    memset(D,INF,sizeof(D));
    D[1][0] = 0;
    int minim = INF;
    for( int i = 0 ; i < n ; i++ ){
        minim = min( minim, H( (1<<n) - 1, i ) + C[i][0] );
    }
    fout << minim;
    return 0;
}