#include <bits/stdc++.h>
using namespace std;

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

int n, a, b,c, m,bitmask, i, j, D[ ( 1 << 18 ) ][ 19 ], x, y, cst[20][20], oo = 1000000000, rsp = oo;

vector < int > G[20];

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

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

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

    for( i = 1 ; i <= m ; i++ )
    {
        fin>>a>>b>>c;
        G[ a ].push_back( b );
        cst[ a ][ b ] = c;
    }


    D[1][0] = 0;

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

    rsp = oo;

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

    if( rsp == oo )
        fout<<"Nu exista solutie";
    else
        fout<<rsp;

    return 0;
}