#include <bits/stdc++.h>
using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");
// #define f cin
// #define g cout
vector<vector<int>> cst(20, vector<int>(20, INT_MAX));
int n, m;
vector<vector<int>> dp(263000, vector<int>(19, INT_MAX));
int solve(int, int);
int32_t main()
{

    f >> n >> m;
    for (int x, y, c; m; m--)
    {
        f >> x >> y >> c;
        cst[y][x] = c;
    }
    dp[1][0] = 0;
    for (int config = 1; config < (1 << n); config++)
        for (int lst = 0; lst < n; lst++)
            if (dp[config][lst] != INT_MAX)
                if (config & (1 << lst))
                    for (int ne = 0; ne < n; ne++)
                        if (!(config & (1 << ne)) && cst[lst][ne] != INT_MAX)
                            dp[config | (1 << ne)][ne] = min(dp[config | (1 << ne)][ne],
                                                             dp[config][lst] + cst[lst][ne]);
    int rez = INT_MAX;
    for (int i = 1; i < n; i++)
        if (dp[(1 << n) - 1][i] != INT_MAX && cst[i][0] != INT_MAX)
            rez = min(rez, dp[(1 << n) - 1][i] + cst[i][0]);
    if (rez != INT_MAX)
        g << rez;
    else
        g << "Nu exista solutie";
    return 0;
}