#include <fstream>
#include <vector>

#define INF 2147483000
#define NMAX 20

using namespace std;

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

vector<int> A[NMAX];
int Cost[NMAX][NMAX];
int C[NMAX][NMAX];

int main()
{
    int n, m;
    int x, y, c;
    fin >> n >> m;

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

    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y >> c;
        A[y].push_back(x);
        Cost[x][y] = c;
    }

    C[1][0] = 0;

    for (int i = 0; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j)
            if (i & (1 << j))
                for (vector<int>::iterator it = A[j].begin(); it != A[j].end(); ++it)
                    if (C[i ^ (1 << j)][*it] != INF) C[i][j] = min(C[i][j], C[i ^ (1 << j)][*it] + Cost[*it][j]);
    int sol = INF;
    for (vector<int>::iterator it = A[0].begin(); it != A[0].end(); ++it)
        if (C[(1 << n) - 1][*it] != INF) sol = min(sol, C[(1 << n) - 1][*it] + Cost[*it][0]);

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