#include <cstdio>
#include <vector>
#define inf 0xffffffff
#define put2(k) (1<<k)
#define minim(a,b) (a<b)?(a):(b)
using namespace std;

vector <int> a[20];
vector <int> :: iterator it;
unsigned int cost[20][20];
unsigned int v[300000][20];
int n,m;

unsigned int hamilton(int k) {
	for (int i=1;i<=put2(n)-1;i++) {
		for (int j=0;j<n;j++) {
			if (i==1 && j==0) v[i][j] = 0;
			else v[i][j] = inf;
			if ((i & put2(j)) != 0) {
				for (it = a[j].begin();it != a[j].end();it++) {
					int putere = put2(*it);
					if ((i & putere) != 0) 
						if (v[i^put2(j)][*it] != inf) v[i][j] = minim(v[i][j],cost[*it][j] + v[i^put2(j)][*it]);
				}
			}
		}
	}
	unsigned int dist = inf;
	for (it = a[0].begin();it != a[0].end();it++) {
		if (v[put2(n)-1][*it] != inf) dist = minim(dist,v[put2(n)-1][*it]+cost[*it][0]);
	}
	return dist;
}

int main() {
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (int i=1;i<=m;i++) {
		int d,b,c;
		scanf("%d %d %d",&d,&b,&c);
		cost[d][b] = c;
		a[b].push_back(d);
	}
	unsigned int res = hamilton(1);
	if (res != inf) printf("%u\n",res);
	else printf("Nu exista solutie\n");
	return 0;
}