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

#define MAXN 19
#define INF 0x3f3f3f3f
int n, m, c[1 << MAXN][MAXN], d[MAXN][MAXN];
vector <int> g[MAXN];
typedef vector <int>::iterator iter;

int main ()
{
    fstream fin ("hamilton.in", ios::in);
    fstream fout ("hamilton.out", ios::out);

    memset (d, 0x3f, MAXN * MAXN * sizeof (int));
    memset (c, 0x3f, MAXN * (1 << MAXN) * sizeof (int));

    fin >> n >> m;
    for (int i = 0, x, y, z; i < m; ++i) {
        fin >> x >> y >> z;
        g[x].push_back (y);
        d[y][x] = z;
    }

    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]);
    }

    sol == INF ? (fout << "Nu exista solutie" << endl) : (fout << sol << endl);

    fin.close ();
    fout.close ();
    return 0;
}