#include <cstdio>
#include <vector>
using namespace std;
const int NMAX = 25;
const int BMAX = 1 << 20;
const int INF = 2000000000;
struct Muchie {
    int x, cost;
};
vector <Muchie> vec[NMAX];
int dp[BMAX][NMAX];

int main() {
    int n, m;
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        int x, y, cost;
        scanf("%d%d%d", &x, &y, &cost);
        vec[x].push_back({y, cost});
    }
    for(int masca = 0; masca < (1 << n); masca++) {
        for(int i = 0; i <= n; i++) {
            dp[masca][i] = INF;
        }
    }
    dp[1][0] = 0;
    for(int masca = 2; masca < (1 << n); masca++) {
        for(int u = 0; u < n; u++) {
            if((masca & (1 << u)) != 0) {
                for(auto nr : vec[u]) {
                    int v = nr.x;
                    if((masca & (1 << v)) != 0 && u != v) {
                        if(dp[masca][v] > dp[masca - (1 << v)][u] + nr.cost) {
                            dp[masca][v] = dp[masca - (1 << v)][u] + nr.cost;
                        }
                    }
                }
            }
        }
    }
    int sol = INF;
    for(int i = 1; i < n; i++) {
        for(auto nr : vec[i]) {
            if(nr.x == 0) {
                sol = min(sol, nr.cost + dp[(1 << n) - 1][i]);
            }
        }
    }
    if(sol == INF) {
        printf("Nu exista solutie\n");
        return 0;
    }
    printf("%d\n", sol);
    return 0;
}