#include <algorithm>
#include <fstream>
#include <cmath>

using namespace std;

const int NMAX= 18, INF= ( 1 << 30 );

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

int N, M;
int d[NMAX+1][1 << (NMAX+1)], c[NMAX+1][NMAX+1];


int hamilton( int nod, int config )
{
    if ( d[nod][config] != 0 )
    {
        return d[nod][config];
    }
    if ( config == ( 1 << (N + 1) ) - 2 )
    {
        if ( c[nod][1] != 0 )
        {
            d[nod][config] = c[nod][1];
        }
        else d[nod][config] = INF;
    }
    else
    {
        int aux, b= INF;

        for ( int i= 2; i<= N; ++i )
        {
            if ( (config & (1 << i) ) == 0 && c[nod][i])
            {
                aux = hamilton( i, config | (1 << i) ) + c[nod][i];
                b = min( b, aux );
            }
        }
        d[nod][config] = b;
    }
    return d[nod][config];
}

int main()
{
    int A, B, C;
    in >> N >> M;

    for( int i= 1; i<=M; ++i )
    {
        in >> A >> B >> C;
        ++A;
        ++B;
        c[A][B]= C;
    }

    int ans = hamilton( 1, ( 1 << 1 ) );

    if ( ans == INF ) out << "Nu exista solutie" << '\n';
    else out << ans << '\n';

    return 0;
}