#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 18
#define MaskMax 262145
#define inf 0x3f3f3f3f

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

int N, M;

int Cost[Nmax][Nmax], D[MaskMax][Nmax];
bool Viz[MaskMax][Nmax];
vector < int > G[Nmax];

int Dinamica( int nod, int mask ){

    if( Viz[mask][nod] )
        return D[mask][nod];

    Viz[mask][nod] = 1;

    vector < int > :: iterator it;
    for( it = G[nod].begin(); it != G[nod].end(); ++it )
        if( ( 1 << *it ) & mask ){
            if( *it == 0 && ( mask^(1<<nod)) != 1 ) continue;
            D[mask][nod] = min( D[mask][nod], Dinamica( *it, mask^(1<<nod) ) + Cost[*it][nod] );
        }

    return D[mask][nod];
}

int main(){

    fin >> N >> M;

    memset( D, inf, sizeof(D) );

    int x, y;
    while( M-- ){
        fin >> x >> y;
        fin >> Cost[x][y];
        G[y].push_back(x);
    }

    int FullMask = (1 << N) - 1;
    for( int i = 0; i < N; ++i )
        D[1<<i][i] = 0;

    int Sol = inf;

    vector < int > :: iterator it;

    for( it = G[0].begin(); it != G[0].end(); ++ it )
        Sol = min( Sol, Dinamica( *it, FullMask ) + Cost[*it][0] );

    if( Sol == inf )
        fout << "Nu exista solutie";
    else
        fout << Sol;

    return 0;
}