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

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

int N, M, X, Y, Z, minim, tmpmsk, V[(1 << DIM) + 2];
int D[(1 << DIM) + 2][DIM + 1], C[DIM + 1][DIM + 1];
int tmpmsk2, v1, v2;

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;
    }

    for( int i = 0; i <= DIM; i ++)
        V[1 << i] = i;

    D[1][0] = 0;

    for( int msk = 3; msk < 1 << N; msk += 2 ) {

        tmpmsk = msk;
        while( tmpmsk ) {

            v1 = V[tmpmsk & (-tmpmsk)];
            tmpmsk -= tmpmsk & (-tmpmsk);

            if( v1 == 0 ) continue;
            else {

                tmpmsk2 = msk - (1 << v1);
                while( tmpmsk2 ) {

                    v2 = V[tmpmsk2 & (-tmpmsk2)];
                    tmpmsk2 -= tmpmsk2 & (-tmpmsk2);

                    D[f(msk)][v1] = min( D[f(msk)][v1], D[f(msk - (1 << v1))][v2] + C[v2][v1] );
                }
            }
        }
    }

    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;
}