#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 18;
const int MAX_M = 1 << MAX_N;
const int INF = numeric_limits<int>::max() / 4;

int dp[MAX_N][MAX_M];
int G[MAX_N][MAX_N];

int N, M;

int cycle(int nodAnterior, int state)
{
    if (dp[nodAnterior][state] != -1)
        return dp[nodAnterior][state];

    int sol = INF;

    if (state == (1 << N) - 1)
    {
        if (G[nodAnterior][0] != INF)
            sol = G[nodAnterior][0];
        else
            sol = INF;
    }
    else
    {
        for (int i = 0; i < N; ++i)
        {
            if (((state & (1 << i)) == 0) && G[nodAnterior][i] != INF)
            {
                sol = min(sol, cycle(i, state ^ (1 << i)) + G[nodAnterior][i]);
            }
        }
    }

    return dp[nodAnterior][state] = sol;
}

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

    in >> N >> M;

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            G[i][j] = INF;

    while (M--)
    {
        int x, y, c;
        in >> x >> y >> c;

        G[x][y] = c;
    }

    memset(dp, -1, sizeof(dp));

    int tmp = cycle(0, 1);

    if (tmp == INF)
        out << "Nu exista solutie\n";
    else
        out << tmp << "\n";

    return 0;
}