#include <fstream>
#include <vector>
#define INF 1000000000
using namespace std;
ofstream fout ("hamilton.out");
ifstream fin ("hamilton.in");
int dp[270000][18],cost[20][20],sol,a,b,c,i,j,n,m,lung;
vector < int > w[20];
int main()
{
    fin>>n>>m;
    for( i = 0 ; i < n ; i++ )
        for( j = 0 ; j < n ; j++ )
            cost[ i ][ j ] = INF;
    for( i = 1 ; i <= m ; i++ )
    {
        fin>>a>>b>>c;
        cost[ a ][ b ] = c;
        w[ b ].push_back( a );
    }
    lung = ( 1 << n );
    for( i = 0 ; i < lung ; i++ )
        for( j = 0 ; j < n ; j++ )
            dp[ i ][ j ] = INF;
    dp[ 1 ][ 0 ] = 0;
    for( i = 1 ; i < lung ; i++ )
    {
        for( j = 0 ; j < n ; j++ )
        {
            if( ( i & ( 1 << j ) ) == 0 )
            {
                for( auto it : w[ j ] )
                {
                    if( i & ( 1 << it )  )
                        dp[ ( i | ( 1 << j ) ) ][ j ] = min( dp[ ( i | ( 1 << j ) ) ][ j ] , dp[ i ][ it ] + cost[ it ][ j ] );
                }
            }
        }
    }
    sol = INF;
    for( i = 0 ; i < n ; i++ )
    {
        sol = min( sol , dp[ lung - 1 ][ i ] + cost[ i ][ 0 ] );
    }
    if( sol == INF )
        fout<<"Nu exista solutie";
    else
        fout<<sol;
}