#include <bits/stdc++.h>

using namespace std;

const int INF = (1 << 30);
const int NMAX = 19;
const int SMAX = (1 << NMAX) + 10;
int N, M;
vector <int> graph[NMAX];
int cost[NMAX][NMAX];
int dp[NMAX][SMAX];

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin >> N >> M;
    for (int i = 0;i < N;++i)
        for (int j = 0;j < N;++j)
            cost[i][j] = INF;
    for (int i = 1;i <= M;++i)
    {
        int u, v, c;
        fin >> u >> v >> c;
        graph[u].push_back(v);
        cost[u][v] = c;
    }
    for (int i = 0;i < N;++i)
        for (int state = 0;state < (1 << N);++state)
            dp[i][state] = INF;
    dp[0][1] = 0;
    for (int state = 1;state < (1 << N);++state)
        for (int i = 0;i < N;++i)
            if ((state & (1 << i)) > 0 && dp[i][state] != INF)
                for (auto& j : graph[i])
                    if ((state & (1 << j)) == 0)
                    {
                        int newstate = (state ^ (1 << j));
                        dp[j][newstate] = min(dp[j][newstate], dp[i][state] + cost[i][j]);
                    }
    int answer = INF;
    for (int i = 1;i < N;++i)
        if (dp[i][(1 << N) - 1] != INF && cost[i][0] != INF)
            answer = min(answer, dp[i][(1 << N) - 1] + cost[i][0]);
    if (answer == INF)
        fout << "Nu exista solutie\n";
    else
        fout << answer << "\n";
    fin.close();
    fout.close();
    return 0;
}