#include <bits/stdc++.h>
using namespace std;
ifstream in ("hamilton.in") ;
ofstream out ("hamilton.out") ;
const int NR = 20 ;
const int oo =  100000002;
vector < int > v [ NR ] ;
int n , m ,x , y , c , dist [ NR ][ NR ] , i , j , cost [ 1 << NR ][ NR ] , sol = oo ;
int main ()
{
    in >> n >> m ;

    for ( i = 0 ; i <= n ; ++ i )
    for ( j = 0 ; j <= n ; ++ j )   dist [ i ][ j ] = oo ;

    for ( i = 0 ; i < ( 1 << n ) ; ++ i )
    for ( j = 0 ; j <= n ; ++ j )   cost [ i ][ j ] = oo ;

    cost [ 1 ][ 0 ] = 0 ;
    while ( m -- )
    {
        in >> x >> y >> c ;
        dist [ x ][ y ] = c ;
        v [ y ].push_back( x ) ;
    }

    for ( i = 0 ;  i < ( 1 << n ) ; ++ i )
    for ( j = 0 ; j < n ; j ++ )
    if ( i & ( 1 << j ) )
        for ( vector < int > :: iterator it = v [ j ].begin() ; it != v [ j ].end() ; ++ it )
    if ( i & ( 1 << *it  ) )
    cost [ i ][ j ] = min ( cost [ i ][ j ] , dist [ *it ][ j ] + cost [ i ^ ( 1 << j  ) ][ *it ] ) ;


    for ( vector < int > :: iterator it = v [ 0 ].begin() ; it != v [ 0 ].end() ; ++ it )
        sol = min ( sol , dist [ *it ][ 0 ] + cost [ ( 1 << n ) - 1 ][ *it ] ) ;

    if ( sol != oo )    out << sol ;
    else                out << "Nu exista solutie" ;
}