#include<cstdio>
#include<algorithm>
#include<vector>
#define MAXN 20
#define INF 20000000
#define MAXbit 263000
FILE *f=fopen("hamilton.in","r"), *g=fopen("hamilton.out","w");

using namespace std;

vector < int > v[MAXN];

int N, M, C[MAXbit][MAXN], Cost[MAXN][MAXN], Rez;

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

    fscanf(f,"%d %d\n",&N,&M);
    for(i=1;i<=M;i++){
        fscanf(f,"%d %d %d\n",&x,&y,&z);
        v[y].push_back(x);
        Cost[y][x] = z;
    }

}

void Hamilton(){
int i, j, k, N2, XOR;

    N2 = 1 << N;

    for(i=0;i<N2;i++)
        for(j=0;j<N;j++)
            C[i][j] = INF;
    C[1][0] = 0;

    for( i = 2; i < N2; i++ )
        for( j = 0; j < N; j++ )
             if (i & (1<<j)) //if( i ^ ( 1 << j ) < i )
                for( k = 0; k < v[j].size(); k++ ){

                    //XOR = i ^ ( 1 << v[j][k] );
                    if (i & (1<<v[j][k])) //if( XOR < i )
                        C[i][j] = min( C[ i ^ ( 1 << j ) ][ v[j][k] ] + Cost[j][ v[j][k] ], C[i][j] );

                }
    Rez = INF;
    for(i=0;i<v[0].size();i++)
        Rez = min( C[N2-1][ v[0][i] ] + Cost[0][ v[0][i] ] , Rez );

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

int main(){

    Citire();
    Hamilton();

return 0;
}