#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int maxn = 20, inf = 1 << 30;

struct xy {
    int x, y;
};

int n, m;
vector <int> v[maxn];
int cost[maxn][maxn];
int d[(1 << maxn)][maxn];

int main() {
    int i, j, x, y, z, ans;

    f >> n >> m;
    for(i = 1; i <= m; i ++) {
        f >> x >> y >> z;
        v[y].push_back(x); // invers
        cost[x][y] = z;
    }

    for(i = 0; i < (1 << n); i ++) {
        for(j = 0; j < n; j ++) {
            d[i][j] = inf;
        }
    }
    d[1][0] = 0;

    for(i = 0; i < (1 << n); i ++) {
        for(j = 0; j < n; j ++) {
            if((i & (1 << j)) != 0) {
                for(auto u : v[j]) {
                    if((i & (1 << u)) != 0) {
                        d[i][j] = min(d[i][j], d[i ^ (1 << j)][u] + cost[u][j]);
                    }
                }
            }
        }
    }
    
    ans = inf;
    /*
    for(i = 0; i < n; i ++) {
        if(cost[i][0] != 0) {
            ans = min(ans, d[(1 << n) - 1][i] + cost[i][0]);
        }
    }
    */
    for(auto u : v[0])
        ans = min(ans, d[(1 << n) - 1][u] + cost[u][0]);

    if(ans != inf)
        g << ans << '\n';
    else
        g << "Nu exista solutie\n";

    return 0;
}