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

int n, m;
vector<int> a[21];
int cost[21][21];
int dp[(1 << 22)][21];
int sol;
const int Inf = 1e9;

void read() {
    int i, x, y, c, j;

    ifstream f("hamilton.in");
    f >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            cost[i][j] = Inf;

    for (i = 0; i < m; i++) {
        f >> x >> y >> c;
        a[y].emplace_back(x);
        cost[x][y] = c;
    }
    f.close();
}

void solve() {
    int i, j, k;
    for (i = 0; i < (1 << n); i++)
        for (j = 0; j < n; j++)
            dp[i][j] = Inf;

    dp[1][0] = 0;
    for (i = 0; i < (1 << n); i++)
        for (j = 0; j < n; j++)
            if (i & (1 << j))
                for (k = 0; k < a[j].size(); k++)
                    if (i & (1 << a[j][k]))
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][a[j][k]] + cost[a[j][k]][j]);

    sol = Inf;
    for (i = 0; i < a[0].size(); i++)
        sol = min(sol, dp[(1 << n) - 1][a[0][i]] + cost[a[0][i]][i]);
}

void output() {
    ofstream g("hamilton.out");
    if (sol == Inf)
        g << "Nu exista solutie";
    else
        g << sol;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}