/*
    SMEN: BackTrack
*/

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <ctime>
#include <cstdlib>

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

int minim = INF, M[DIM], S[DIM], C[DIM][DIM], N, T;
vector <int> E[DIM]; int X, Y, Z, nr;

void back_track( int pos, int node, int cost ) {
    M[node] = 1; nr ++;

    if( pos == N ) {
        minim = min( minim, cost + C[node][N / 2] );
        M[node] = 0; nr ++;
        return;
    }

    vector <int> :: iterator it;
    for( it = E[node].begin(); it != E[node].end(); it ++ ) {
        int next_node = *it;

        if( nr >= 1000000 ) return;

        if( !M[next_node] && cost + C[node][next_node] < minim )
            back_track( pos + 1, next_node, cost + C[node][next_node] );
    }

    M[node] = 0;
    return;
}

int my_random( int i ) { return rand() % i; }

int main () {

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

    srand( time(0) );

    scanf( "%d %d", &N, &T );
    memset( C, INF, sizeof( C ));

    for( int i = 0; i <= N; i ++ ) {
        C[i][i] = 0;
        random_shuffle( E[i].begin(), E[i].end() );
    }

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

    back_track( 1, N / 2, 0 );

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

    return 0;
}