#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

#define MAXN 20
#define MAXX 1000000
#define inf 0x3f3f3f3f

vector<int> g[MAXN];
int n, m, cost[MAXN][MAXN], pd[MAXX][MAXN], sol;

int main() {
    int i, j, k, x, y;
    fin >> n >> m;
    for (i = 1; i <= m; ++i) {
        fin >> x >> y;
        g[y].push_back(x);
        fin >> cost[x][y];
    }

    for (i = 0; i < (1 << n); ++i)
        for (j = 0; j < n; ++j)
            pd[i][j] = inf;

    pd[1][0] = 0;

    for (i = 0; i < (1 << n); ++i)
        for (j = 0; j < n; ++j) {
            if (i & (1 << j))
                for (k = 0; k < g[j].size(); ++k)
                    if (i & (1 << g[j][k]))
                        pd[i][j] = min(pd[i][j], pd[i ^ (1 << j)][g[j][k]] + cost[g[j][k]][j]);
        }
    sol = inf;

    for (i = 0; i < g[0].size(); ++i)
        sol = min(sol, pd[(1 << n) - 1][g[0][i]] + cost[g[0][i]][0]);

    if (sol == inf)
        fout << "Nu exista solutie";
    else
        fout << sol << "\n";
    return 0;
}