#include <fstream>
#include <vector>

using namespace std;

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

const int PermMAX = 1<<18;
const int NMAX = 19;
const int INF = 1000000000;
int n,m,i,j,x,y,c,ans;
int Ham[PermMAX][NMAX],Cost[NMAX][NMAX];
vector < int > Graf[ NMAX ];

int main()
{
    fin>>n>>m;
    for( i = 0 ; i < (1 << n) ; i++ )
    for( j = 0 ; j <= n ; j++ )
        Ham[ i ][ j ] = INF;
    for( i = 0 ; i <= n ; i++ )
    for( j = 0 ; j <= n ; j++ )
        Cost[ i ][ j ] = INF;

    for( i = 1 ; i <= m ; i++ )
    {
        fin>>x>>y>>c;
        Graf[ y ].push_back( x );
        Cost[ x ][ y ] = c;
    }

    Ham[ 1 ][ 0 ] = 0;
    for( i = 1 ; i <= (1 << n ) - 1 ; i++ )
        for( j = 0 ; j < n ; j++ )
            if( i & (1<<j) )
                for( vector<int>::iterator k = Graf[ j ].begin() ; k != Graf[ j ].end() ; k++ )
                    Ham[ i ][ j ] = min( Ham[ i ][ j ] , Ham[ i ^ ( 1 << j ) ][ *k ] + Cost[ *k ][ j ] );

    ans = INF;
    for( i = 0 ; i < n ; i++ )
    {
        ans = min( ans , Ham[ ( 1 << n ) - 1 ][ i ] + Cost[ i ][ 0 ] );
    }
    if( ans == INF )
        fout<<"Nu exista solutie";
    else
        fout<<ans;

return 0;
}