#include <fstream>
#include <vector>

using namespace std;

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

const int PermMAX = 1<<18;
const int NMAX = 19;
const int INF = 1000000000;
int n,m,i,j,x,y,c,ans;
int D[PermMAX][NMAX],Cost[NMAX][NMAX];
vector < int > Graf[ NMAX ];

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>>c;
        Graf[ x ].push_back( y );
        Cost[ x ][ y ] = c;
    }

    ///43210
    ///[10110] [0] inv
    ///[10110] [1] oo
    ///[10110] [2] oo
    ///[10110] [3] inv
    ///[10110] [4] oo
    ///[00001][0] = 0

    D[1][0] = 0;
    for( int bitmask = 0 ; bitmask < (1<<n) ; bitmask++ )
    {
        for( int nod = 0 ; nod < n ; nod++ )
        {
            if( ( bitmask & (1<<nod) ) != 0 )
            {
                ///D[bitmask][nod]
                for( auto urm : Graf[ nod ] )
                {
                    if( ( bitmask & (1<<urm) ) == 0 )
                    {
                        D[ bitmask | (1<<urm) ][ urm ] = min( D[ bitmask ][ nod ] + Cost[ nod ][ urm ] , D[ bitmask | (1<<urm) ][ urm ] );
                    }
                }
            }
        }
    }

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

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

return 0;
}