#include <fstream>
#include <vector>

using namespace std;

const int NrStari = 1 << 18;
const int NrNoduri = 18;
const int INF = 1000000000;

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

vector < int > Graf[ 20 ];
int D[ NrStari ][ NrNoduri ], Cost[ NrNoduri ][ NrNoduri ],i,j,n,m,x,y,c,ans;

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

    for( i = 0 ; i < 1 << n ; i++ )
    for( j = 0 ; j <= n ; j++ )
        D[ 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;
        Graf[ y ].push_back( x );
        fin>>Cost[ x ][ y ];
    }

    D[ 1 ][ 0 ] = 0;
    for( i = 2 ; i < 1 << n ; i++ )
    for( j = 0 ; j < n ; j++ )
        if( i & ( 1 << j ) )
            for( auto it : Graf[ j ] )
                D[ i ][ j ] = min( D[ i ][ j ] , D[ i ^ ( 1 << j ) ][ it ] + Cost[ it ][ j ] );

    ans = INF;
    for( i = 0 ; i < n ; i++ )
        ans = min( ans , D[ ( 1 << n ) - 1 ][ i ] + Cost[ i ][ 0 ] );

    if( ans == INF )
        fout<<"Nu exista solutie";
    else
        fout<<ans;

    return 0;
}