#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;
}
void calcul()
{
    for ( int i = 0; i <= NN; i++ )
        for ( int j = 0; j < N; j++ )
            C[i][j] = INF;

    C[1][0] = 0;

    for ( int i = 0; i <= NN; i++ )
        for ( int j = 0; j < N; j++ )
            if ( i & ( 1 << j ) )
                for ( int &x : G[j] )
                {
                    if ( i & ( 1 << x ) )
                        C[i][j] = min ( C[i][j], C[i ^ ( 1 << j )][x] + Cost[x][j] );
                }
}
int main()
{
    int Sol = INF;
    citire();
    calcul();

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

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

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