#include<fstream>
#include<vector>

using namespace std;

ifstream fin( "hamilton.in" ); ofstream fout( "hamilton.out" );

const int nmax = 18;
const int cmax = (1 << nmax);
const int inf = 59652323;
int c[ nmax + 1 ][ nmax + 1 ];
int dp[ cmax + 1 ][ nmax + 1 ];

vector< int > g[ nmax + 1 ];

inline int min2( int a, int b ) {
    return ( a < b ? a : b );
}
int main() {
    int n, m;
    fin >> n >> m;

    for( int i = 0; i < n; ++ i ) {
        for( int j = 0; j < n; ++ j ) {
            c[ i ][ j ] = inf;
        }
    }

    for( int i = 0; i < m; ++ i ) {
        int x, y;
        fin >> x >> y;
        g[ x ].push_back( y );
        fin >> c[ x ][ y ];
    }

    for( int i = 0; i < (1 << n); ++ i ) {
        for( int j = 0; j < n; ++ j ) {
            dp[ i ][ j ] = inf;
            if ( i & (1 << j) ) {
                if ( i == (1 << j) ) {
                    dp[ i ][ j ] = 0;
                }
                for( int k = 0; k < n; ++ k ) {
                    if ( i & (1 << k) && k != j ) {
                        dp[ i ][ j ] = min2( dp[ i ][ j ], dp[ i - (1 << j) ][ k ] + c[ k ][ j ] );
                    }
                }
            }
        }
    }

    int ans = inf;
    for( vector< int >::iterator it = g[ 0 ].begin(); it != g[ 0 ].end(); ++ it ) {
        ans = min2( ans, dp[ (1 << n) - 1 ][ *it ] + c[ *it ][ 0 ] );
    }

    if ( ans == inf ) {
        fout << "Nu exista solutie\n";
    } else {
        fout << ans << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}