#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int INF = 0x3f3f3f3f;

int N, M, sol;
int dp[(1 << 18) + 5][18], cost[20][20];
vector<int> V[20];

int main()
{
    for (int i = 1; i <= 18; ++i)
        for (int j = 1; j <= 18; ++j)
            cost[i][j] = INF;

    fin >> N >> M;
    for (int i = 1, x, y, c; i <= M; ++i)
    {
        fin >> x >> y >> c;
        V[y].push_back(x);
        cost[x][y] = c;
    }
    for (int i = 1; i <= (1 << N); ++i)
        for (int j = 0; j <= N; ++j)
            dp[i][j] = INF;

    dp[1][0] = 0;

    for (int i = 1; i <= (1 << N); ++i)
        for (int j = 0; j <= N - 1; ++j)
            if (i & (1 << j))
                for (vector<int>::iterator it = V[j].begin(); it != V[j].end(); ++it)
                    if (i & (1 << *it))
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][*it] + cost[*it][j]);

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

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

    fin.close();
    fout.close();
    return 0;
}