#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f ( "hamilton.in" );
ofstream g ( "hamilton.out" );
const int NMAX = 19,
          XMAX = ( 1 << 18 ),
          INF = 1 << 30;
int N, M, NN, Cost[NMAX][NMAX], C[XMAX][NMAX];
vector<int>G[NMAX];
void citire()
{
    int x, y;
    f >> N >> M;

    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < N; j++ )
            Cost[i][j] = INF;

    for ( int i = 1; i <= M; i++ )
    {
        f >> x >> y;
        G[y].push_back ( x );
        f >> Cost[x][y];
    }

    NN = ( 1 << N ) - 1;
}
int calcul ( int cfg, int j )
{
    if ( C[cfg][j] == -1 )
    {
        C[cfg][j] = INF;

        for ( int &x : G[j] )
        {
            if ( cfg & ( 1 << x ) )
            {
                if ( x == 0 && cfg != ( 1 << j ) + 1 )
                    continue;

                C[cfg][j] = min ( C[cfg][j], calcul ( cfg ^ ( 1 << j ), x ) + Cost[x][j] );
            }
        }
    }

    return C[cfg][j];
}
int main()
{
    int Sol = INF;
    citire();

    for ( int i = 0; i <= NN; i++ )
        for ( int j = 0; j < N; j++ )
            C[i][j] = -1;

    C[1][0] = 0;

    for ( int &nod : G[0] )
        Sol = min ( Sol, calcul ( NN, nod ) + Cost[nod][0] );

    if ( Sol == INF )
        g << "Nu exista solutie";
    else g << Sol;

    f.close();
    g.close();
    return 0;
}