#include<cstdio>
using namespace std;
//varianta fara memoizare
const int nMax = 19;
const int mMax = nMax * nMax;
const int INF = 100000000;

int urm[mMax], nod[mMax], lst[nMax];
int cost[nMax][nMax], C[1 << nMax][nMax];
int nre;

inline void adauga(int x, int y){
    nod[++nre] = y;
    urm[nre] = lst[x];
    lst[x] = nre;
}

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

int main (){
    FILE *in = fopen("hamilton.in","r");
    FILE *out = fopen("hamilton.out","w");

    int n, m;
    fscanf(in,"%d%d", &n, &m);

    for(int i = 0, x, y; i < m ; ++i){
        fscanf(in,"%d%d", &x, &y);
        fscanf(in,"%d", &cost[x][y]);
        adauga(y, x);
    }

    for(int i = 0 ; i < (1 << n) ; ++i)
        for(int j = 0 ; j < n ; ++j)
            C[i][j] = INF;
    C[1][0] = 0;

    int pos, vec;
    for(int i = 0 ; i < (1 << n) ; ++i){
        for(int j = 0 ; j < n ; ++j){
            if(i & (1 << j)){
                pos = lst[j]; vec = nod[pos];
                while(pos){
                    if(i & (1 << vec)){
                        C[i][j] = minim(C[i][j], C[i ^ (1 << j)][vec] + cost[vec][j]);
                    }
                    pos = urm[pos];
                    vec = nod[pos];
                }
            }
        }
    }

    int best = INF;
    pos = lst[0]; vec = nod[pos];
    while(pos){
        best = minim(best, C[(1 << n) - 1][vec] + cost[vec][0]);
        pos = urm[pos]; vec = nod[pos];
    }

    fprintf(out,"%d\n", best);
    return 0;
}