#include <stdio.h>
#include <vector>
#define N 18
#define INF 18000000

struct edge { int node, cost; };
std::vector <struct edge> g[N];
int ans[N][(1 << (N + 1)) - 1];

inline bool isInMask( int a, int x ) { return (x >> a) % 2; }
inline int removeBit( int a, int x ) { return x ^ (1 << a); }
bool hasEdge( int a, int b ) {
    for ( struct edge x : g[a] )
        if ( x.node == b )
            return true;
    return false;
}

int main() {
    FILE *fin, *fout;
    int n, m, x, y, cost, i;

    fin = fopen( "hamilton.in", "r" );
    fscanf( fin, "%d%d", &n, &m );
    for ( int i = 0; i < m; i ++ ) {
        fscanf( fin, "%d%d%d", &x, &y, &cost );
        g[x].push_back( {y, cost} );
    }
    fclose( fin );

    i = 0;
    for ( int x = 0; x < (1 << n); x ++ ) {
        i = 0;
        if ( isInMask( i, x ) ) {
            for ( struct edge neighbour : g[i] ) {
                if ( isInMask( neighbour.node, x ) && ans[i][removeBit( neighbour.node, x )] != 0 ) {
                    ans[neighbour.node][x] = ans[i][removeBit( neighbour.node, x )] + neighbour.cost;
                    printf( "%d %d %d\n", neighbour.node, x, ans[neighbour.node][x] );
                }
            }
        }
    }

    /**
    25
    16 + 8 + 1
    11001
    **/

    int min = INF;
    for ( int i = 0; i < n; i ++ ) {
        if ( ans[i][(1 << n) - 1] != 0 && ans[i][(1 << n) - 1] < min && hasEdge( i, 0 ) )
            min = ans[i][(1 << n) - 1];
    }

    fout = fopen( "hamilton.out", "w" );
    fprintf( fout, "%d\n", min );
    fclose( fout );
    return 0;
}