#include <fstream>
#include <iomanip>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>

#define INF 0x3f3f3f3f

using namespace std;

#ifdef DEBUG
string name = "data";
#else
string name = "hamilton";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

#define MAXN 18

int n, m;

int c[MAXN][MAXN];
int best[1 << MAXN][MAXN];
vector<int> g[MAXN];

void gen(int k, int bit, int nrOne, vector<int> &result) {
    if (bit > (n - nrOne)) {
        return;
    }
    
    if (nrOne == 0) {
        result.push_back(k);
        return;
    }
    
    gen(k | (1 << bit), bit + 1, nrOne - 1, result);
    gen(k, bit + 1, nrOne, result);
}

vector<int> genNr(int nrOne) {
    vector<int> result;
    
    if (nrOne == 0) {
        result.push_back(0);
        return result;
    }
    
    gen(1, 1, nrOne - 1, result);
    
    return result;
}

int main() {
    
    fin >> n >> m;
    
    memset(c, 0x3f, sizeof(c));
    
    for (int i = 0; i < m; ++i) {
        int x,y,z;
        fin >> x >> y >> z;
        c[x][y] = z;
        g[y].push_back(x);
    }
    
    memset(best, 0x3f, sizeof(best));
    
    best[1][0] = 0;
    
    for (int i = 2; i <= n; ++i) {
        auto v = genNr(i);
        
        for (int x: v) {
            for (int bit = 1; bit < n; ++bit) {
                for (auto j: g[bit]) {
                    if (!(x & (1 << j))) {
                        continue;
                    }
                    
                    if (c[j][bit] != INF) {
                        best[x][bit] = min(best[x][bit], best[x & (~(1 << bit))][j] + c[j][bit]);
                    }
                }
            }
        }
    }
    
    int bestest = INF;
    
    for (auto x: g[0]) {
        bestest = min(bestest, best[(1 << n) - 1][x] + c[x][0]);
    }
    
    if (bestest == INF) {
        fout << "Nu exista solutie";
    } else {
        fout << bestest;
    }
    
    return 0;
}