#include <iostream>
#include <vector>
using namespace std;
#define INF 999999999

int N, M, Cost[19][19], C[1 << 19][19], S[19];
vector<int> G[19];

int main() {
    FILE *f1=fopen("hamilton.in", "r"), *f2=fopen("hamilton.out", "w");
    int i, j, p, q, c;
    fscanf(f1, "%d %d\n", &N, &M);
    for(i=0; i<N; i++) {
         for(j=0; j<N; j++) {
              Cost[i][j]=INF;
         }
    }
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d %d\n", &p, &q, &c);
         G[q].push_back(p);
         Cost[p][q]=c;
    }
    for(i=0; i<(1 << N); i++) {
         for(j=0; j<N; j++) {
              C[i][j]=INF;
         }
    }
    C[1][0]=0;
    for(i=0; i<(1 << N); i++) {
         memset(S, 0, sizeof(S));
         p=i;
         for(j=0; j<N; j++) {
              if(p%2) S[j]=1;
              p=p/2;
         }
         for(j=0; j<N; j++) {
              if(S[j]) {
                   for(int k=0; k<G[j].size(); k++) {
                        if(S[G[j][k]]) {
                             C[i][j]=min(C[i][j], C[i ^ (1 << j)][G[j][k]] + Cost[G[j][k]][j]);
                        }
                   }
              }
         }
    }
    int sol=INF;
    for(int k=0; k<G[0].size(); k++) {
         sol=min(sol, C[(1 << N)-1][G[0][k]] + Cost[G[0][k]][0]);
    }
    if(sol==INF) { fprintf(f2, "Nu exista solutie\n"); }
    else { fprintf(f2, "%d\n", sol); }
    fclose(f1); fclose(f2);
    return 0;
}