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

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

#define MaxN 18
#define INF 0x3f3f3f3f

int n, m;
vector<int>G[MaxN];
int D[1 << MaxN][MaxN]; // D[i][j] = costul pana la nodul j cu config-ul din i;
int Cost[MaxN][MaxN];

int main() {

    fin >> n >> m;

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

    for ( int i = 0; i < (1 << n); ++i )
        for ( int j = 0; j < n; ++j )
            D[i][j] = INF;

    D[1][0] = 0;

    for ( int i = 1, x, y, z; i <= m; ++i ) {
        fin >> x >> y >> z;
        G[y].push_back(x);
        Cost[x][y] = z;
    }

    for ( int st = 1; st < (1 << n); ++st )
        for ( int i = 0; i < n; ++i )
            if ( st & (1 << i) )
                for ( const auto p : G[i] )
                    if ( st & (1 << p) )
                        D[st][i] = min(D[st][i], D[st ^ (1 << i)][p] + Cost[p][i]);


    int sol = INF;

    for ( int i = 0; i < n; ++i )
        if ( D[(1 << n) - 1][i] != INF  )
            sol = min(sol, D[(1 << n) - 1][i] + Cost[i][0] );

    if ( sol != INF )
        fout << sol << '\n';
    else
        fout << "Nu exista solutie\n";

    fin.close();
    fout.close();
    return 0;
}