#include <stdio.h>
#define INF 1000000000
#define MAXN 18
#define MAXM 306
int val[MAXM+1], next[MAXM+1], cost[MAXM+1], lista[MAXN], d[1<<MAXN][MAXN];
int main(){
    int n, m, i, j, x, p, ans;
    FILE *fin, *fout;
    fin=fopen("hamilton.in", "r");
    fout=fopen("hamilton.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d%d%d", &val[i], &x, &cost[i]);
        next[i]=lista[x];
        lista[x]=i;
    }
    for(i=0; i<(1<<n); i++){
        for(j=0; j<n; j++){
            d[i][j]=INF;
        }
    }
    d[1][0]=0;
    for(i=0; i<(1<<n); i++){
        for(j=0; j<n; j++){
            if((i&(1<<j))!=0){
                p=lista[j];
                while(p!=0){
                    if(((i&(1<<j))!=0)&&(d[i][j]>d[i^(1<<j)][val[p]])){
                        d[i][j]=d[i^(1<<j)][val[p]]+cost[p];
                    }
                    p=next[p];
                }
            }
        }
    }
    ans=INF;
    p=lista[0];
    while(p!=0){
        if(ans>d[(1<<n)-1][val[p]]+cost[p]){
            ans=d[(1<<n)-1][val[p]]+cost[p];
        }
        p=next[p];
    }
    if(ans==INF){
        fprintf(fout, "Nu exista solutie\n");
    }
    fprintf(fout, "%d\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}