#include <stdio.h>
using namespace std;

const int NMAX = 20;
const int NMAXPOW2 = 1 << NMAX;

int N, M;
int muchie[NMAX][NMAX];
int Ciclu[NMAX][NMAXPOW2];

int ciclu(int nodAnterior, int exista){
    int SOL = 0x3fffffff;
    if(Ciclu[nodAnterior][exista] == 0){
        if(exista == ((1 << N) - 1)){
            if(muchie[nodAnterior][0] != 0){
                return muchie[nodAnterior][0];
            }
            return 0x3fffffff;
        }else{
            int i;
            SOL = 0x3fffffff;
            int solPotentiala = 0;
            for(i = 0; i < N; i++){
                if((exista & (1 << i)) == 0){
                    if(muchie[nodAnterior][i] != 0){
                        solPotentiala = muchie[nodAnterior][i] + ciclu(i, exista ^ (1 << i));
                        if(SOL > solPotentiala){
                            SOL = solPotentiala;
                        }
                    }
                }
            }
        }
        Ciclu[nodAnterior][exista] = SOL;
    }
    return Ciclu[nodAnterior][exista];
}

int main(){
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    int x, y, c;
    int i, j;
    scanf("%d%d", &N, &M);
    for(i = 1; i <= M; i++){
        scanf("%d %d %d", &x, &y, &c);
        muchie[x][y] = c;
    }
    int SOL;
    SOL = ciclu(0, 1 << 0);
    if(SOL == 0x3fffffff) {
        printf("Nu exista solutie");
    }else{
        printf("%d", SOL);
    }
}