// Testez doar bkt-ul...
#include <climits>
#include <fstream>

#define DMAX 100

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

int n, m;
int ad[DMAX][DMAX];

int lgMin;
int trMin[DMAX];

int lg;
int tr[DMAX];
bool vis[DMAX];

void bkt(int pos) {
    if (lg >= lgMin)
        return;

    if (pos == n + 1) {
        if (!ad[tr[n]][1])
            return;

        lg += ad[tr[n]][1];
        if (lg < lgMin) {
            lgMin = lg;
            for (int i = 1; i <= n; i++)
                trMin[i] = tr[i];
        }

        lg -= ad[tr[n]][1];
        return;
    }

    for (int i = 2; i <= n; i++)
        if (!vis[i] && ad[tr[pos - 1]][i]) {
            vis[tr[pos] = i] = true;
            lg += ad[tr[pos - 1]][i];

            bkt(pos + 1);

            vis[i] = false;
            lg -= ad[tr[pos - 1]][i];
        }
}

int main() {
    int x, y, z;
    lgMin = INT_MAX;

    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> z;
        x++; y++;
        ad[x][y] = z;
    }

    vis[tr[1] = 1] = true;
    bkt(2);

    if (lgMin == INT_MAX)
        fout << "Nu exista solutie\n";
    else
        fout << lgMin << '\n';

    fout.close();
    return 0;
}