#include <fstream>
#include <vector>

#define Max_N 18
#define INF 1000000000

using namespace std;

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

int n, m, C[(1 << Max_N) + 5][Max_N + 5], Cost[Max_N + 5][Max_N + 5];
vector < int > V[Max_N + 5];

inline int Minim(int a, int b)
{
    if (a < b) return a;
    return b;
}

int main()
{
    fin >> n >> m;

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            Cost[i][j] = INF;
        }
    }

    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 = 0; i < (1 << n); i ++) {
        for (int j = 0; j < n; j ++) {
            C[i][j] = INF;
        }
    }

    C[1][0] = 0;
    for (int i = 0; i < (1 << n); i ++) {
        for (int j = 0; j < n; j ++) {
            if (i & (1 << j)) {
                for (int k = 0; k < V[j].size(); k ++) {
                    if (i & (1 << V[j][k])) {
                        C[i][j] = Minim(C[i][j], C[i ^ (1 << j)][V[j][k]] + Cost[V[j][k]][j]);
                    }
                }
            }
        }
    }

    int sol = INF;
    for (int i = 0; i < V[0].size(); i ++) {
        sol = Minim(sol, C[(1 << n) - 1][V[0][i]] + Cost[V[0][i]][0]);
    }

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

    fout.close();
    return 0;
}