#include <stdio.h>
#include <string.h>
typedef struct GRAF{
    int n;
    int **A;
}GRAF;
FILE *pf, *pf2;
int minim = 99999999;
void afisare(int k, int *st,GRAF G){
    int sum = 0;
    for (int i = 1 ; i < k ; i ++){
        sum = sum + G.A[st[i]][st[i+1]];
    }
    sum = sum + G.A[st[k]][st[1]];
    if (sum < minim)
        minim = sum;
}
void bt(int k, GRAF G,int *st,int *p){
    for (int i = 0 ; i < G.n ; i ++){
        if (!p[i]){
            p[i] =1;
            if (k == G.n && G.A[i][st[1]] == 0);
            else
            if (k >= 2 && G.A[st[k-1]][i] == 0);
            else {
                st[k] = i;
                if (k == G.n)
                    afisare(k,st,G);
                bt(k+1,G,st,p);
            }
            p[i] = 0;
        }
    }
}
int main(){
    pf = fopen("hamilton.in","r");
    pf2 = fopen("hamilton.out","w");
    GRAF G;
    int m;
    fscanf(pf,"%d%d",&G.n,&m);
    G.A = calloc(G.n+1,sizeof(int*));
    for (int i = 0 ; i < G.n+1 ; i ++)
        G.A[i] = calloc(G.n+1,sizeof(int));
    for (int i = 0 ; i < m ; i ++){
        int x,y,cost;
        fscanf(pf,"%d%d%d",&x,&y,&cost);
        G.A[x][y] = cost;
    }
    int *st = calloc(G.n+1,sizeof(int));
    int *p = calloc(G.n+1,sizeof(int));
    st[0] = -1;
    bt(1,G,st,p);
    if (minim == 99999999)
        fprintf(pf2,"Nu exista solutie");
    else
        fprintf(pf2,"%d",minim);
}
/*

5 10
0 1 9
0 3 8
1 0 7
1 2 1
1 4 3
2 0 5
2 4 4
3 2 6
4 3 7
4 1 1


*/