#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 20;
const int Nmax2 = ( 1 << 20 );
const int oo = 0x3fffffff;

int N, M;
int A[Nmax][Nmax];
int D[Nmax][Nmax2];

int ciclu( int nodAnterior, int exista )
{
    if ( D[nodAnterior][exista] )
            return D[nodAnterior][exista];

    int SOL = oo;

    if ( exista == ( 1 << N ) - 1 )
    {
        if ( A[nodAnterior][0] )
        {
            SOL = A[nodAnterior][0];
        }
    }
    else
    {
        for ( int i = 1; i < N; ++i )
        {


            if ( ( ( exista & ( 1 << i ) ) == 0 ) && A[nodAnterior][i] )
            {
                //cout<<"DA";
                int sol = A[nodAnterior][i] + ciclu( i, exista ^ ( 1 << i ) );

                if ( SOL > sol )
                        SOL = sol;
            }
        }
    }

    D[nodAnterior][exista] = SOL;
    cout << nodAnterior << " " << exista << " " << SOL << "\n";

    return D[nodAnterior][exista];
}


int main()
{
    ifstream f("hamilton.in");
    ofstream g("hamilton.out");

    f >> N >> M;

    for ( int i = 1, a, b, c; i <= M; ++i )
    {
        f >> a >> b >> c;

        A[a][b] = c;
    }

    int SOL = ciclu( 0, 1 );

    g << SOL << "\n";

    return 0;
}