#include <fstream>

using namespace std;

ifstream F("hamilton.in");
ofstream G("hamilton.out");

int n, m, x, y, C, a[ 20 ][ 20 ], d[ 262150 ][ 20 ], sol;
const int inf = 1000000005;

int main()
{
    F >> n >> m;
    for( int i = 1; i <= m; ++ i )
    {
        F >> x >> y >> C;
        a[ x ][ y ] = C;
    }
    for( int i = 0; i < ( 1 << n ); ++ i )
        for( int j = 0; j < n; ++ j )
            d[ i ][ j ] = inf;
    d[ 1 ][ 0 ] = 0;
    for( int i = 1; i < ( 1 << n ); ++ i )
    {
        for( int j = 0; j < n; ++ j )
        {
            if( i & ( 1 << j ) )
            {
                for( int k = 0; k < n; ++ k )
                {
                    if( j != k && ( i & ( 1 << k ) ) && a[ k ][ j ] )
                    {
                        d[ i ][ j ] = min( d[ i ][ j ], d[ i ^ ( 1 << j ) ][ k ] + a[ k ][ j ]);
                    }
                }
            }
        }
    }
    sol = inf;
    for( int i = 0; i < n; ++ i )
        if( a[ i ][ 0 ] )
            sol = min( sol, d[ ( 1 <<  n ) - 1 ][ i ] + a[ i ][ 0 ] );
    if( sol != inf ) G << sol;
    else G << "Nu exista solutie";
    return 0;
}