#include <fstream>
#define DIM 18
#define INF 2000000001
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n, m, x, y, cost, nr, mini, c[DIM][DIM], d[1 << DIM][DIM];
int main() {
    fin >> n >> m;
    while (m--) {
        fin >> x >> y >> cost;
        c[x][y] = cost;
    }
    nr = (1 << n) - 1;
    for (int i = 1; i <= nr; i++)
        for (int j = 0; j < n; j++)
            d[i][j] = INF;
    d[1][0] = 0;
    for (int st = 1; st <= nr; st++)
        for (int i = 0; i < n; i++)
            if ((st & (1 << i)) != 0)
                for (int j = 0; j < n; j++)
                    if (c[i][j] != 0 && (st & (1 << j)) == 0) {
                        int nxt = (st + (1 << j));
                        d[nxt][j] = min(d[nxt][j], d[st][i] + c[i][j]);
                    }
    mini = INF;
    for (int i = 1; i < n; i++)
        if (c[i][0] != 0)
            mini = min(mini, d[nr][i] + c[i][0]);
    if (mini == INF)
        fout << "Nu exista solutie";
    else
        fout << mini;
    return 0;
}