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

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

struct muchie {
    int vecin, cost;
};

const int mxN = 18;
int dp[1 << mxN][mxN];
int n, m;
vector<muchie> G[mxN];

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        G[a].push_back({b, c});
    }

    int FULL = (1 << n) - 1;

    // Initializare cu INF
    for (int mask = 0; mask <= FULL; mask++)
        for (int i = 0; i < n; i++)
            dp[mask][i] = INT_MAX;

    dp[1][0] = 0; // start din nodul 0, doar el vizitat

    for (int mask = 1; mask <= FULL; mask++) {
        for (int last = 0; last < n; last++) {
            if (dp[mask][last] == INT_MAX) continue;
            if (!(mask & (1 << last))) continue;

            for (muchie x : G[last]) {
                if (mask & (1 << x.vecin)) continue; // deja vizitat

                int newMask = mask | (1 << x.vecin);
                if (dp[mask][last] + x.cost < dp[newMask][x.vecin])
                    dp[newMask][x.vecin] = dp[mask][last] + x.cost;
            }
        }
    }

    int ans = INT_MAX;
    for (int last = 1; last < n; last++) {
        if (dp[FULL][last] == INT_MAX) continue;
        for (muchie x : G[last]) {
            if (x.vecin == 0)
                ans = min(ans, dp[FULL][last] + x.cost);
        }
    }

    if (ans == INT_MAX)
        fout << "Nu exista solutie";
    else
        fout << ans;

    return 0;
}