#include <cstring>

#include <fstream>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;

const int MAXN = 18;
const int MAXX = (1 << 18);

int cost[MAXN][MAXN];
int dp[MAXX][MAXN];

vector<int> G[MAXN];

int doit(int config, int i)
{
    if (dp[config][i] == -1) {
        dp[config][i] = INF;

        vector<int>::iterator it;
        for (it = G[i].begin(); it != G[i].end(); ++it) {
            if (config & (1 << (*it))) {
                if (*it == 0 && config != (1 << i) + 1)
                    continue;
                dp[config][i] = min(dp[config][i], 
                        doit(config ^ (1 << i), *it) + cost[*it][i]);
            }
        }
    }

    return dp[config][i];
}

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

    memset(cost, INF, sizeof(cost));

    int N, M;
    fin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int x, y, cst;
        fin >> x >> y >> cst; 
        G[y].push_back(x);
        cost[x][y] = cst;
    }
    fin.close();

    memset(dp, -1, sizeof(dp));
    dp[1][0] = 0;

    int sol = INF;
    vector<int>::iterator it;
    for (it = G[0].begin(); it != G[0].end(); ++it)
        sol = min(sol, doit((1 << N) - 1, *it) + cost[*it][0]);

    if (sol < INF / 2)
        fout << sol << "\n";
    else
        fout << "Nu exista solutie\n";
    fout.close();

    return 0;
}