#include<cstdio>
#define MAX_N 18
#define oo 0x3f3f3f3f
using namespace std;

int C[MAX_N][MAX_N], T[MAX_N+1], n, m, minCost, Cost;
bool used[MAX_N];

void Back(int k) {
    if(k == n + 1) {
        if(C[T[k-1]][T[1]] && Cost + C[T[k-1]][T[1]] < minCost)
                minCost = Cost + C[T[k-1]][T[1]];
    } else {
        for(int i=0; i<n; i++)
            if(C[T[k-1]][i] && !used[i]) {
                T[k] = i;
                used[i] = true;
                Cost += C[T[k-1]][i];
                if(Cost <= minCost) Back(k+1);
                used[i] = false;
                Cost -= C[T[k-1]][i];
            }
    }
}

int main() {
    int i, x, y, c;
    FILE *fin, *fout;
    fin = fopen("hamilton.in","r");
    fout = fopen("hamilton.out","w");
    fscanf(fin,"%d%d",&n,&m);
    for(i=0; i<m; i++) {
        fscanf(fin,"%d%d%d",&x,&y,&c);
        C[x][y] = c;
    }
    minCost = oo;
    for(i=0; i<n; i++) {
        T[1] = i;
        used[i] = true;
        Cost = 0;
        Back(2);
        used[i] = false;
    }
    if(minCost == oo)
        fprintf(fout,"Nu exista solutie\n");
    else fprintf(fout,"%d\n",minCost);
    fclose(fin);
    fclose(fout);
    return 0;
}