#include <fstream>
#include <vector>

using namespace std;

const int MAXN = 19;
const int MAXX = 262145;
const int INF = 100000000;

int n, m, sol;
int cost[MAXN][MAXN];
int B[MAXX][MAXN];
vector <int> A[MAXN];

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

    f >> 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 x, y;

        f >> x >> y;
        A[y].push_back(x);
        f >> cost[x][y];
    }

    for (int i = 0; i < 1 << n; ++i)
        for (int j = 0; j < n; ++j) B[i][j] = INF;

    B[1][0] = 0;

    for (int i = 0; i < 1 << n; ++i)
        for (int j = 0; j < n; ++j)
            if (i & (1<<j))
                for (size_t k = 0; k < A[j].size(); ++k)
                    if (i & (1<<A[j][k]))
                        B[i][j] = min(B[i][j], B[i ^ (1<<j)][ A[j][k] ] + cost[ A[j][k] ][j]);

    sol = INF;
    for (size_t i = 0; i < A[0].size(); ++i)
        sol = min(sol, B[(1<<n) - 1][ A[0][i] ] + cost[ A[0][i] ][0]);

    if (sol == INF) g << "Nu exista solutie" << endl;
    else g << sol << endl;

    return 0;
}