#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 20 ;
const int Nmaxpow2 = 1 << Nmax ;

const int INF = 0x3fffffff ;

int N , M ;

int mat[ Nmax ][ Nmax ];
int was[ Nmax ][ Nmaxpow2 ];

int ciclu( int ant , int exista ){

    //cout << ant << " " << exista << endl ;

    if( was[ ant ][ exista ] )
        return was[ ant ][ exista ];

    int sol = INF ;

    if( exista == ( 1 << N ) - 1 )
    {
        if( mat[ ant ][ 0 ] )
            sol = mat[ ant ][ 0 ];

    }else{

        int auxSol ;

        sol = INF ;

        for( int i = 1 ; i < N ; i++ ){

            if( mat[ ant ][ i ] && ( ( exista & ( 1 << i ) ) == 0 ) ){

                auxSol = mat[ ant ][ i ] + ciclu( i , exista ^ ( 1 << i ) );

                if( auxSol < sol )
                    sol = auxSol ;

            }

        }

    }

    was[ ant ][ exista ] = sol ;
    return sol ;

}

int main()
{

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

    f >> N >> M ;

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

        f >> a >> b >> c ;

        mat[a][b] = c ;
    }

    g << ciclu( 0 , 1 ) ;

    return 0;
}