#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>

using namespace std;

#define NMAX 18
#define INFINIT 1 << 30

int cost[NMAX][NMAX];
long long d[NMAX][1 << NMAX];
bool inCoada[NMAX][1 << NMAX];

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

    int n, m;
    fin >> n >> m;

    while (m--) {
        int x, y, c;
        fin >> x >> y >> c;
        cost[x][y] = c;
    }

    for (int i = 0; i <= n; ++i)
        for (int j = 0; j < (1 << n); ++j)
            d[i][j] = INFINIT;

    queue< pair<int, int> > q;
    q.push(make_pair(0, 0));
    d[0][0] = 0;

    while (!q.empty()) {
        int nod = q.front().first;
        int conf = q.front().second;
        q.pop();

        inCoada[nod][conf] = false;

        // cout << nod << " " << bitset<NMAX>(conf) << " cost: " << d[nod][conf] << "\n";

        for (int i = 0; i < n; ++i) {
            if (!(conf & (1 << i)) && cost[nod][i] > 0) {
                int costNou = d[nod][conf] + cost[nod][i];
                int confNou = conf | (1 << i);

                // cout << "incerc " << i << "\n";

                if (costNou < d[i][confNou]) {
                    // cout << "update la " << i << ": " << costNou << "(" << d[i][confNou] << ")\n";

                    d[i][confNou] = costNou;
                    if (!inCoada[i][confNou]) {
                        q.push(make_pair(i, confNou));
                        inCoada[i][confNou] = true;
                    }
                }
                // else cout << "dar costul este " << d[i][confNou] << "\n";
            }
        }
    }


    int raspuns = d[0][(1 << n) - 1];

    if (raspuns < INFINIT)
        fout << raspuns << "\n";
    else fout << "Nu exista solutie";

    return 0;
}