#include <bits/stdc++.h>

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[NMAX+2][1 << NMAX];
int N, M;

void init()
{
    memset(dp, INF, sizeof(dp));
    dp[0][1] = 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) == 0) || i == j || m[j][i] == 0 ) continue;
                dp[i][mk] = min(dp[i][mk], dp[j][mk ^ (1 << i)] + m[j][i]);
            }
            cerr << i << " " << mk << ": " << dp[i][mk] << '\n';
        }
    }
    int best = INF;
    for( int i = 1;  i < N;  ++i ) if( m[i][0] )
        best = min(best, dp[i][(1 << N) - 1] + m[i][0]);
    if( best == INF ) {
        out << "Nu exista solutie\n";
        return 0;
    }
    out << best << '\n';
    return 0;
}