#include <fstream>
#include <algorithm>
using namespace std;

ifstream is("hamilton.in");
ofstream os("hamilton.out");

#define INF 1000000000

int N, M, x, y, z, Sol;
int C[18][18];
int D[1<<18][18];

int main()
{
    is >> N >> M;
    for ( int i = 0; i < N; ++i )
        for ( int j = 0; j < (1<<N); ++j )
            D[j][i] = INF;

    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y >> z;
        C[x][y] = z;
    }

    D[1][0] = 0;

    for ( int i = 0; i < (1<<N) ; ++i )
        for ( int j = 0; j < N; ++j )
            if ( i & (1<<j) )
                for ( int k = 0; k < N; ++k )
                    if ( i & (1<<k) && C[k][j] )
                        D[i][j] = min(D[i][j],D[i^(1<<j)][k] + C[k][j] );

    Sol = INF;

    for ( int i = 1; i < N; ++i)
        if ( C[i][0] )
        Sol = min(Sol,D[(1<<N) - 1][i] + C[i][0]);

    os << Sol;


    is.close();
    os.close();
}