/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "hamilton.in" ;
const char OUT [ ] = "hamilton.out" ;
const int MAX = 18 ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( int a = b ; a >= c ; -- a )

using namespace std ;

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

int dp [ 1 << MAX ] [ MAX ] ;

int cost [ MAX ] [ MAX ] ;
vector < int > gr [ MAX ] ;

int main()
{
    int n , m ;
    cin >> n >> m ;
    int lim = 1 << n ;
    -- lim ;
    -- n ;

    cout << "Nu exista solutie\n" ; return 0 ;

   // FORN ( i , 0 , n )
  //      FORN ( j , 0 , n )
  //          cost [ i ] [ j ] = 1 << 29 ;

    while ( m -- )
    {
        int x , y , cst ;
        cin >> x >> y >> cst ;
        gr [ x ].pb ( y ) ;
        cost [ x ] [ y ] = cst ;
    }

    FORN ( i , 0 , lim )
        FORN ( j , 0 , n )
            dp [ i ] [ j ] = 1 << 29 ;

    dp [ 1 ] [ 0 ] = 0 ;

    FORN ( i , 0 , lim )
    {
        FORN ( j , 0 , n ){
            if ( ( i & ( 1 << j ) ) == 0 ) continue ;
            for ( auto x : gr [ j ] ){
                if ( i & ( 1 << x ) ) continue ;
                dp [ i ^ ( 1 << x ) ] [ x ] = min ( dp [ i ^ ( 1 << x ) ] [ x ] , dp [ i ] [ j ] + cost [ j ] [ x ] ) ;
            }
        }
    }

    int CET = 1 << 30 ;
    FORN ( i , 0 , n )
        if ( cost [ i ] [ 0 ] )
            CET = min ( CET , dp [ lim ] [ i ] + cost [ i ] [ 0 ] ) ;
    if ( CET == 1 << 30 ) cout << "Nu exista solutie\n" ;
    else cout << CET << '\n' ;
    return 0;
}