#include <fstream>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n, m, cost[18][18], dp[1 << 18][18], x, y, c;

int main()
{
    f >> n >> m;

    while (m--) {
        f >> x >> y >> c;

        cost[x][y] = c;
    }

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

    dp[1][0] = 0;

    for (int k = 1; k < (1 << n); ++k) {
        for (int i = 0; i < n; ++i) {
            if (k & (1 << i)) {
                for (int j = 0; j < n; ++j) {
                    if (!(k & (1 << j)) && cost[i][j]) {
                        dp[k ^ (1 << j)][j] = min(dp[k ^ (1 << j)][j], dp[k][i] + cost[i][j]);
                    }
                }
            }
        }
    }

    int minim = 1 << 30;

    for (int i = 0; i < n; ++i) {
        if (cost[i][0]) {
            minim = min(minim, dp[(1 << n) - 1][i] + cost[i][0]);
        }
    }

    if (minim != (1 << 30)) {
        g << minim;
    }
    else {
        g << "Nu exista solutie";
    }

    return 0;
}