#include <cstdio>
#include <algorithm>
#include <cstring>

const int DIM = 17;
const int INF = 0x3f3f3f3f;
using namespace std;

int N, M, X, Y, Z, minim;
int D[1 << DIM + 2][DIM + 1], C[DIM + 1][DIM + 1];

inline int f( int value ) {
    return (value + 1) / 2;
}

int main () {

    freopen( "hamilton.in" ,"r", stdin  );
    freopen( "hamilton.out","w", stdout );

    memset( C, INF, sizeof( C ));
    memset( D, INF, sizeof( D ));

    scanf( "%d %d", &N, &M );
    for( int i = 1; i <= M; i ++ ) {
        scanf( "%d %d %d", &X, &Y, &Z);
        C[X][Y] = Z;
    }

    D[1][0] = 0;

    for( int msk = 3; msk < 1 << N; msk += 2 ) {
    for( int i = 1; i < N; i ++ ) {
        if( (msk >> i) & 1 ) {
            for( int j = 0; j < N; j ++ ) {
                if( (i != j) && ((msk >> j) & 1) )
                    D[f(msk)][i] = min( D[f(msk)][i], D[f(msk - (1 << i))][j] + C[j][i] );
            }
        }
    }}

    minim = INF;
    for( int i = 0; i < N; i ++ )
        minim = min( minim, D[f((1 << N) - 1)][i] + C[i][0] );

    if( minim == INF )
        printf( "Nu exista solutie\n" );
    else
        printf( "%d\n", minim );

    return 0;
}