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

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

#define NMAX 25
#define INF 1000000000

vector<pair<int, int>> GT[NMAX];
int dp[(1 << 18) + 5][NMAX];

int main() {
    int n, m;
    fin >> n >> m;
    while (m--) {
        int x, y, c;
        fin >> x >> y >> c;
        GT[y].push_back({x, c});
    }

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

    dp[1][0] = 0;

    for (int i = 3; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                int conf = i - (1 << j);
                for (auto it : GT[j]) {
                    if (conf & (1 << it.first)) {
                        dp[i][j] = min(dp[i][j], dp[conf][it.first] + it.second);
                    }
                }
            }
        }
    }

    int minim = INF;
    for (auto it : GT[0]) {
        minim = min(minim, dp[(1 << n) - 1][it.first] + it.second);
    }

    if (minim == INF) {
        fout << "Nu exista solutie";
    } else {
        fout << minim;
    }
    return 0;
}