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

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

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

inline int solve( int msk, int i ) {

    if( msk == 0 ) return INF;
    if( D[msk][i] != INF ) return D[msk][i];

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

    return D[msk][i];
}

int main () {

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

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

    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; minim = INF;

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

    printf( "%d\n", minim );

    return 0;
}