#include <fstream>
#include <vector>

using namespace std;

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

int D[ ( 1 << 18 ) ][ 19 ], cst[20][20];

int n, m, bitmask, nod, i, j, x, y, c, oo = 1000000000, rsp, urm;

vector < int > G[20];

int main()
{

using namespace std;
    f>>n>>m;

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

    for ( i = 1; i <= m; i++ )
    {
        f>>x>>y>>c;

        G[x].push_back(y);

        cst[x][y] = c;

    }

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

    D[1][0] = 0;

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

    rsp = oo;

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

    if ( rsp == oo )
    {
        g<<"Nu exista solutie" ;
    }
    else
    {
        g<<rsp;
    }

}