#include <fstream>
#include <cstring>
#include <iostream>

using namespace std;

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

const int NMAX = 18;
const int INF  = 0x3f3f3f3f;

int m[NMAX+2][NMAX+2];
int dp[(1 << NMAX) + 2][NMAX+2];
int N, M;

void init()
{
    memset(dp, INF, sizeof(dp));
    dp[1][0] = 0;
}

int main()
{
    in >> N >> M;
    for( int i = 1;  i <= M;  ++i ) {
        int x,y,c;
        in >> x >> y >> c;
        m[x][y] = c;
    }
    init();
    for( int mk = 1;  mk < (1 << N);  ++mk ) {
        for( int i = 0;  i < N;  ++i ) {
            if( ((1 << i) & mk) == 0 ) continue;
            for( int j = 0;  j < N;  ++j )  {
                if( !((1 << j) & mk) || m[j][i] == 0 ) continue;
                dp[mk][i] = min(dp[mk][i], dp[mk ^ (1 << i)][j] + m[j][i]);
            }
            ///cerr << i << " " << mk << ": " << dp[mk][i] << '\n';
        }
    }
    int best = INF;
    for( int i = 1;  i < N;  ++i ) if( m[i][0] )
        best = min(best, dp[(1 << N) - 1][i] + m[i][0]);
    if( best == INF ) {
        out << "Nu exista solutie\n";
        return 0;
    }
    out << best << '\n';
    return 0;
}