/*
    SMEN: BackTrack
*/

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

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;

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

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

    vector <int> :: reverse_iterator it;
    for( it = E[node].rbegin(); it != E[node].rend(); it ++ ) {
        int next_node = *it;

        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 main () {

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

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

    for( int i = 0; i <= N; i ++ )
        C[i][i] = 0;

    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 );
    printf( "%d\n", minim );

    return 0;
}