#include <memory.h>
#include <vector>
#include <cstdio>

FILE *f=fopen("hamilton.in","r");
FILE *g=fopen("hamilton.out","w");

using namespace std;

const int INF=0x3F3F3F3F;
const int Nmax = 20;

int C[ (1 << (Nmax-2))+ 10 ][Nmax];
int cost[Nmax][Nmax],N,M;
vector<int> lv[Nmax];

void get_g(){
    fscanf(f,"%d%d",&N,&M);
    int a,b,c;
    memset(C,INF,sizeof(C));
    memset(cost,INF,sizeof(cost));
    for(int i = 1; i <= M; ++i){
        fscanf(f,"%d%d%d",&a,&b,&c);
        lv[b].push_back(a);
        cost[a][b]=c;
    }
}

void solve(){
    C[1][0]=0;
    int i,j;
    for(i = 0; i < (1 << N); ++i)
        for(j = 0; j < N; ++j)
            if(i & (1<<j))
                for(vector<int>::iterator it = lv[j].begin();it!=lv[j].end();++it)
                    if(i &  (1 << (*it)))
                        C[i][j] = min(C[i][j], C[i ^ (1<<j)][*it] + cost[*it][j]);

}
void print(){
    int answer = INF;
    for(vector<int>::iterator it = lv[0].begin();it!=lv[0].end();++it)
        answer=min(answer, C[(1 << N) - 1][*it] + cost[*it][0]);
    answer == INF ? fprintf(g,"Nu exista solutie\n") : fprintf(g,"%d",answer);
}
int main()
{
    get_g();
    solve();
    print();
    return 0;
}