#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

#define NMAX 18
#define SMAX 1 << 18
#define INF 0x3f3f3f3f

int N, M;
int cst[NMAX][NMAX];
int din[SMAX][NMAX];
vector<int> V[NMAX];

int main() {
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);

    scanf("%d %d ", &N, &M);

    int i, j, k;
    memset(cst, INF, sizeof(cst));
    for (i = 1; i <= M; i++) {
        int x, y, c;
        scanf("%d %d %d ", &x, &y, &c);
        cst[x][y] = c;
        V[x].push_back(y);
    }

    memset(din, INF, sizeof(din));
    din[1][0] = 0;
    for (i = 1; i < (1 << N); i++) {
        for (j = 0; j < N; j++) {
            if (!((1 << j) & i)) {
                continue;
            }
            for (k = 0; k < V[j].size(); k++) {
                int nod = V[j][k];
                int cost = cst[j][nod];                
                if ((1 << nod) & i) {
                    continue;
                }

                din[i + (1 << nod)][nod] = min(din[i + (1 << nod)][nod], din[i][j] + cost);
            }
        }
    }

    int sol = INF;
    for (i = 0; i < N; i++) {
        sol = min(sol, din[(1 << N) - 1][i] + cst[i][0]);
    }
    if (sol < INF) {
        printf("%d ", sol);
    } else {
        printf("Nu exista solutie\n");
    }
    return 0;
}