#include <vector>
#include <fstream>

using std::vector;
std::ifstream fin("hamilton.in");
std::ofstream fout("hamilton.out");

inline int min(int x, int y) {
    return x < y ? x : y;
}

int main() {
    int n, m; fin >> n >> m;
    vector<vector<int>> ad(n, vector<int>(n, 1e9));

    for (int i = 0; i < m; i++) {
        int x, y, z; fin >> x >> y >> z;
        ad[x][y] = z;
    }

    vector<vector<int>> dp(1 << n, vector<int>(n, 1e9));
    dp[1][0] = 0;

    int nrSubs = 1 << n;
    for (int subs = 3; subs < nrSubs; subs += 2)
        for (int i = 0; i < n; i++)
            if (subs & (1 << i))
                for (int j = 0; j < n; j++)
                    if (subs & (1 << j) && j != i)
                        dp[subs][i] = min(dp[subs][i], dp[subs & ~(1 << i)][j] + ad[j][i]);

    int sol = 1e9;
    for (int i = 1; i < n; i++)
        sol = min(sol, dp[nrSubs - 1][i] + ad[i][0]);

    if (sol == 1e9)
        fout << "Nu exista solutie\n";
    else
        fout << sol << '\n';

    fout.close();
    return 0;
}