#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <ctime>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream ff("hamilton.in");
ofstream gg("hamilton.out");

int n, m, cc[18][18], dd[1<<18][18];
 
void sol(){
	memset(dd, 0x3f, sizeof(dd));
	for(int i=0;i<n;i++) dd[1<<i][i]=0;
	for(int i=0;i<(1<<n);i++)
	for(int j=0;j<n;j++)
	for(int k=0;k<n;k++)
	if(i&(1<<j) && !(i&(1<<k)) && cc[j][k])
		dd[i|(1<<k)][k]=min(dd[i|(1<<k)][k], dd[i][j]+cc[j][k]);
	
	int s = 0x3f3f3f3f;
	for(int i=0;i<n;i++)
	if(cc[i][0])
		s=min(s, dd[(1<<n)-1][i]+cc[i][0]);
	if(s==0x3f3f3f3f) gg << "Nu exista solutie"; else
	gg << s << "\n";
} 
 
int main(){
	int a, b, c;
	ff >> n >> m;
	for(int i=0;i<m;i++){
		ff >> a >> b >> c;
		cc[a][b]=c;
	}
	sol();
}