#include<cstdio>
#include<vector>
#include<algorithm>
#define DIM 20
#define DIM2 262150
#define INF 100000000
FILE *f=fopen("hamilton.in","r"), *g=fopen("hamilton.out","w");

using namespace std;

vector <int> v[DIM];

int N, M, C[DIM][DIM], Hm[DIM2][DIM];

void Citire(){
int i, x, y, c;

    fscanf(f,"%d %d\n",&N,&M);

    for(i=1;i<=M;i++){

        fscanf(f,"%d %d %d\n",&x,&y,&c);

        v[x].push_back(y);
        C[x][y] = c;

    }

}

void Rezolvare(){
int i, j, I, J, K, Nla2, R;

    Nla2 = 1 << N;

    for(i=0;i<=Nla2-1;i++)
        for(j=0;j<=N-1;j++)
            Hm[i][j] = INF;

    Hm[1][0] = 0;

    for(I=3;I<=Nla2-1;I++)  // Configuratia de tip 011010010
        for(J=0;J<=N-1;J++)   // J -> K
            if( I & (1<<J) )
                for(i=0;i<v[J].size();i++){

                    K = v[J][i];    // J -> K

                    if( I & (1<<K) )
                        Hm[I][K] = min( Hm[ I^(1<<K) ][J] + C[J][K], Hm[I][K] );

                }

    R = INF;

    for(i=0;i<=N-1;i++)
        if( C[i][0] != 0 ) // i -> 0
            R = min( Hm[Nla2-1][i] + C[i][0], R );

    if( R == INF )
        fprintf(g,"Nu exista solutie");
    else
        fprintf(g,"%d\n",R);

}

int main(){

    Citire();
    Rezolvare();

return 0;
}