#include <fstream>
#include <vector>
#define pb push_back
using namespace std;

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

int dp [ ( 1 << 18) ][19], cost [20][20];
int n, m, bitmask, nod, x, y, c, oo = 1000000000, rsp, urm;
vector <int> G[20];

int main()
{
    fin >> n >> m;

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

    for ( int i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> c;
        G[x].pb(y);
        cost[x][y]=c;
    }

    for ( int i = 0 ; i <= ( 1 << n) - 1 ; i++ )
    {
        for( int j = 0 ; j < n ; j++ )
            dp[i][j]=oo;
    }
    dp[1][0]=0;
    for ( bitmask = 0 ; bitmask < ( 1 << n ) ; bitmask++ )
    {
        for( nod = 0 ; nod < n ; nod++ )
        {
            if( (bitmask & ( 1 << nod )) != 0 )
            {
                for( auto urm : G[nod] )
                {
                    if( ( bitmask & ( 1 << urm )) == 0 )
                    {
                        dp[ ( bitmask | ( 1 << urm ) ) ][ urm ] = min ( dp[ ( bitmask | ( 1 << urm ) ) ][ urm ], dp[ bitmask ][ nod ] + cost[ nod ][ urm ] ) ;
                    }
                }
            }
        }
    }
    rsp = oo;

    for ( int i = 0 ; i < n ; i++ )
    {
        if( cost [i][0] != oo )
        {
            rsp = min ( rsp, dp[ ( 1 << n ) - 1 ][ i ] + cost[i][0] );
        }
    }

    if ( rsp == oo )
    {
        fout<<"Nu exista solutie" ;
    }
    else
    {
        fout<<rsp;
    }
    fin.close();
    fout.close();
    return 0;
}