#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");

vector<int> vv[18];
int n, m, cc[18][18], dd[1<<18][18];
 
void sol(){
	memset(dd, 0x3f, sizeof(dd));
	dd[1][0]=0;
	
	for(int i=0;i<(1<<n);i++)
	for(int j=0;j<n;j++)
	if(i&(1<<j))
	for(int k=0;k<(int)vv[j].size();k++)
	if(i&(1<<vv[j][k]))
		dd[i][j]=min(dd[i][j], dd[i^(1<<j)][vv[j][k]]+cc[vv[j][k]][j]);
		
	for(int i=0;i<1<<n;i++){
	for(int j=0;j<n;j++) cout << dd[i][j] << " "; cout << "\n"; }
	
	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;
	memset(cc, 0x3f, sizeof(cc));
	for(int i=0;i<m;i++){
		ff >> a >> b >> c;
		cc[a][b]=c;
		vv[b].push_back(a);
	}
	sol();
}