#include <bits/stdc++.h>
using namespace std;
string np = "hamilton";
ifstream f(np + ".in");
ofstream g(np + ".out");

// #define f cin
// #define g cout

int n, m;
vector<vector<int>> cost(20, vector<int>(20, INT_MAX));
vector<vector<int>> dp(263000, vector<int>(20, INT_MAX));

int main()
{
    f >> n >> m;
    for (int a, b, c; m; m--)
        f >> a >> b >> c, cost[b][a] = c;

    dp[1][0] = 0;
    for (int cfg = 1; cfg < (1 << n); cfg++)
        for (int lst = 0; lst < n; lst++)
            if (dp[cfg][lst] != INT_MAX)
                if (cfg & (1 << lst))
                    for (int ne = 0; ne < n; ne++)
                        if (!(cfg & (1 << ne)) and cost[lst][ne] != INT_MAX)
                            dp[cfg | (1 << ne)][ne] = min(dp[cfg | (1 << ne)][ne], dp[cfg][lst] + cost[lst][ne]);
    int rez = INT_MAX;
    for (int i = 1; i < n; i++)
        if (dp[(1 << n) - 1][i] != INT_MAX and cost[i][0] != INT_MAX)
            rez = min(rez, dp[(1 << n) - 1][i] + cost[i][0]);

    if (rez != INT_MAX)
        g << rez;
    else
        g << "Nu exista solutie";

    return 0;
}