#include <stdio.h>

#define N 18
#define CMAX 1000001
#define INF (N * CMAX)

int c[N][N], cost[1<<N][N];

int min (int a, int b) {
    return a < b ? a : b;
}

int main(void) {
    FILE *in = fopen("hamilton.in", "r");
    int n, m;
    fscanf(in, "%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                c[i][j] = CMAX;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        int x, y;
        fscanf(in, "%d%d", &x, &y);
        fscanf(in, "%d", &c[x][y]);
    }
    fclose(in);
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            cost[i][j] = INF;
        }
    }
    cost[1][0] = 0;
    for (int i = 3; i < (1 << n); i += 2) {
        for (int j = 1; j < n; j++) {
            if (i & (1 << j)) {
                int i_fara_j = (i ^ (1 << j));
                for (int k = 0; k < n; k++) {
                    if (i_fara_j & (1 << k)) {
                        cost[i][j] = min(cost[i][j], cost[i_fara_j][k] + c[k][j]);
                    }
                }
            }
        }
    }
    int cost_min_circ = INF;
    for (int j = 0; j < n; j++) {
        cost_min_circ = min(cost_min_circ, cost[(1<<n)-1][j] + c[j][0]);
    }
    FILE *out = fopen("hamilton.out", "w");
    fprintf(out, "%d\n", cost_min_circ);
    fclose(out);
    return 0;
}