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

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

const int MAXN = 18;
const int MAXMASK = 1 << MAXN;
const long long INF = 1e18;

int n, m;
long long cost[MAXN][MAXN];
long long dp[MAXMASK][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 < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
    }

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

    dp[1][0] = 0;

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == INF) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                if (cost[u][v] == INF) continue;
                int new_mask = mask | (1 << v);
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + cost[u][v]);
            }
        }
    }

    long long result = INF;
    for (int u = 1; u < n; u++) {
        if (cost[u][0] != INF && dp[(1 << n) - 1][u] != INF) {
            result = min(result, dp[(1 << n) - 1][u] + cost[u][0]);
        }
    }

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

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