#include <fstream>
#include <vector>

using namespace std;

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

const int nMax = 1 << 18;
const int oo = 2000000000;
int n, m;
vector<pair<int, int>> g[20];
int dp[nMax][20];

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        fin >> x >> y >> z;
        g[y].push_back({x, z});
    }
    int r = 1 << n;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = oo;
    dp[1][0] = 0;
    for (int i = 1; i < r; i++) {
        if ((i & 1) == 0)
                continue;
        for (int j = 1; j < n; j++) {
            if ((i & (1 << j)) == 0)
                continue;
            for (auto k : g[j]) {
                if ((i &(1 << k.first)))
                    dp[i][j] = min(dp[i][j], dp[(i ^ (1 << j))][k.first] + k.second);
            }
        }
    }
    int sol = oo;
    for (auto i : g[0]) {
        sol = min(sol, dp[r - 1][i.first] + i.second);
    }
    if (sol == oo)
        fout << "Nu exista solutie" << '\n';
    else
        fout << sol << '\n';
    return 0;

}