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

ifstream cin( "hamilton.in" );
ofstream cout( "hamilton.out" );

struct muchie {
    int nod, cost;
};

const int INF = 2e9 + 236;
const int MAX = 20;

vector<muchie> nod[ MAX ];
int dp[ MAX ][ ( 1 << MAX ) + 1 ];
int a[ MAX ][ MAX ];
int x, y, cost;
int n, m;

int main()
{
    cin >> n >> m;

    int right = ( 1 << n );
    for( int i = 0; i < m; i++ ) {
        cin >> x >> y >> cost;
        nod[ x ].push_back( { y, cost } );
        a[ x ][ y ] = cost;
    }

    for( int i = 0; i < n; i++ )
        for( int j = 0; j < right; j++ )
            dp[ i ][ j ] = INF;

    dp[ 0 ][ 1 ] = 0;
    for( int mask = 2; mask < right; mask++ )
        for( int i = 0; i < n; i++ )
            if( ( mask >> i ) & 1 )
                for( auto x : nod[ i ] )
                    if( ( mask >> x.nod ) & 1 )
                        if( dp[ i ][ mask - ( 1 << x.nod ) ] + x.cost < dp[ x.nod ][ mask ] )
                            dp[ x.nod ][ mask ] = dp[ i ][ mask - ( 1 << x.nod ) ] + x.cost;
    int rez = INF;
    for( int i = 0; i < n; i++ )
        if( a[ i ][ 0 ] )
            rez = min( dp[ i ][ right - 1 ] + a[ i ][ 0 ], rez );

    if( rez == INF )
        cout << "Nu exista solutie\n";
    else cout << rez << '\n';
    return 0;
}