#include <fstream>
#include <vector>

#include <iostream>

using namespace std;

const int kInfinite = (1 << 30);

inline int TurnOff(int x, int pos)
{
    return x & (~(1 << pos));
}

inline void Bin(int x, int n)
{
    while (n--) {
        cout << ((x & (1 << n)) ? 1 : 0);
    }
}

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

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

    vector<vector<int>> edges(n, vector<int>(n, 0));
    while (m--) {
        int x, y, c;
        fin >>  x >> y >> c;
        edges[x][y] = c;
    }

    vector<vector<int>> d(n, vector<int>((1 << n), kInfinite));
    int start = 0;
    d[start][(1 << start)] = 0;

    for (int i = 1; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                for (int k = 0; k < n; ++k) {
                    if (k != j && (i & (1 << k)) && edges[k][j] != 0) {
                        int new_cost = d[k][TurnOff(i, j)] + edges[k][j];
                        d[j][i] = min(d[j][i], new_cost);
                    }
                }
            }
        }
    }

    int min_cost = kInfinite;
    for (int i = 0; i < n; ++i) {
        if (edges[i][start]) {
            min_cost = min(min_cost, d[i][(1 << n) - 1] + edges[i][start]);
        }
    }

    if (min_cost == kInfinite) {
        fout << "Nu exista solutie\n";
    } else {
        fout << min_cost << "\n";
    }
    return 0;
}