#include <stdio.h>
#include <stdlib.h>

#define INF 100000

void print_table(unsigned short *tbl, int row, int col) {
    int i, j;
    for (i = 0; i < row; i++) {
        for (j = 0; j < col; j++) {
            printf("%u ", tbl[i*col + j]);
        }
        printf("\n");
    }
    printf("\n");
}

int main() {
    unsigned short *memo, *m;
    int dist[15][15];
    int i, j, s, t, d, V, E, state, before_state, before_dist, min_dist;

    scanf("%d %d", &V, &E);
    for (i = 0; i < V; i++) {
        for (j = 0; j < V; j++) {
            dist[i][j] = 0;
        }
    }
    for (i = 0; i < E; i++) {
        scanf("%d %d %d", &s, &t, &d);
        dist[s][t] = d;
    }

    memo = (unsigned short *)calloc((1<<(V-1)) * (V-1), sizeof(unsigned short));

    state = (1 << (V-1)) - 1;
    for (i = 1; i < V; i++) {
        memo[state * (V-1) + i-1] = dist[0][i];
    }

    while (--state >= 0) {
        for (i = 0; i < V-1; i++) {  // before vertex ..
            if (!(state & (1 << i))) {
                before_state = state | (1 << i);
                before_dist = memo[before_state * (V-1) + i];
                if (before_dist == 0) continue;
                for (j = 0; j < V-1; j++) {
                    if ((state & (1 << j)) && dist[i+1][j+1] > 0) {
                        d = before_dist + dist[i+1][j+1];
                        m = &memo[state * (V-1) + j];
                        if (*m == 0 || d < *m) {
                            *m = d;
                        }
                    }
                }
            }
        }
    }
    min_dist = INF;
    for (i = 0; i < V-1; i++) {
        m = &memo[(1<<i)*(V-1)+i];
        if (!dist[i+1][0] || !(*m)) continue;
        d = *m + dist[i+1][0];
        if (d < min_dist) {
            min_dist = d;
        }
    }

    printf("%d\n", min_dist<INF ? min_dist: -1);

    free(memo);

    return 0;
}