#include <cstring>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

#define MAXN 18
#define inf 0x3f3f3f3f

typedef vector<int>::iterator iter;

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

int n, m;
int c[1 << MAXN][MAXN]; // c[i][j] == costul minim al unui drum care trece prin nodurile din multimea i si se termina in j.
int d[MAXN][MAXN];
vector<int> G[MAXN];

int main()
{
    memset(d, 0x3f, sizeof(d));
    memset(c, 0x3f, sizeof(c));

    f >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        f >> x >> y >> c;
        G[y].push_back(x);
        d[x][y] = c;
    }

    c[1][0] = 0;
    for (int i = 1; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i & (1 << j)) == 0) {
                continue;
            }

            for (iter it = G[j].begin(); it != G[j].end(); it++) {
                if ((i & (1 << *it)) == 0) {
                    continue;
                }
                c[i][j] = min(c[i][j], c[i ^ (1 << j)][*it] + d[*it][j]);
            }
        }
    }

    int sol = inf;
    for (iter it = G[0].begin(); it != G[0].end(); it++) {
        sol = min(sol, c[(1 << n) - 1][*it] + d[*it][0]);
    }

    if (sol == inf) {
        g << "Nu exista solutie" << endl;
    } else {
        g << sol << endl;
    }

    return 0;
}