/*
 * File:   main.cpp
 * Author: petru
 *
 * Created on 2010-09-23
 */


#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define deb(n) fprintf(stderr,"%d ",(n));
#define MULT 0x3f3f3f3f
#define DN 20
#define DX 262150
#define IT vector<int>::iterator
using namespace std;

int n,m,cost[DN][DN],din[DX][DN];
vector<int> graf[DN];

int c(int a, int b) {
    if(din[a][b]==-1) {
        din[a][b]=MULT;
        for(IT it=graf[b].begin();it!=graf[b].end();++it) if(a&(1<<(*it))) {
            if((!(*it)) && a!=((1<<b)+1)) continue;
            din[a][b]=min(din[a][b],c(a^(1<<b),*it)+cost[*it][b]);
        }
    }
    return din[a][b];
}

int main()
{
	int i,rez=MULT,x,y;
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
    scanf("%d %d",&n,&m);
    //for(i=0;i<n;++i) fill(cost[i],cost[i]+n,MULT);
    memset(cost,MULT,sizeof (cost));
    memset(din,-1,sizeof(din));
    for(i=0;i<m;++i) {
        scanf("%d %d",&x,&y);
        scanf("%d",&cost[x][y]);
        graf[y].push_back(x);
    }
    din[1][0]=0;
    for(IT it=graf[0].begin();it!=graf[0].end();++it)
        rez=min(rez,c((1<<n)-1,*it)+cost[*it][0]);
    deb(rez);
    if(rez==MULT) printf("Nu exista solutie");
    else printf("%d",rez);
	return 0;
}