#include<fstream>
#include<cstring>
#define DIM 18
const int 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 == 1 && i == 0 ) return 0;
    if( D[conf][i] != 0  ){
        return D[conf][i];
    }else{
        D[conf][i] = INF;
        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;
    }
    int minim = INF;
    for( int i = 1 ; i < n ; i++ ){
        minim = min( minim, H( (1<<n) - 1, i ) + C[i][0] );
    }
    if( minim == INF ){
        fout << "Nu exista solutie\n";
        return 0;
    }
    fout << minim;
    return 0;
}