#include <bits/stdc++.h>
using namespace std;
ifstream in ("hamilton.in") ;
ofstream out ("hamilton.out") ;
const int NR = 20 ;
const int oo = 1000002 ;
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 ][ 1 ] = 0 ;
    while ( m -- )
    {
        in >> x >> y >> c ;
        ++ y , ++ x ;
        dist [ x ][ y ] = c ;
        v [ y ].push_back( x ) ;
    }

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


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

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