#include<stdio.h>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

FILE *in, *out;

//definitions
#define pb push_back
#define pii pair<int,int>
#define mp make_pair

//constants
const int sz = 18;
const int oo = (1<<30)-1;

//variables
int nodes, edges;
int node1, node2, cost;

vector<pii> graph[sz];

bool viz[sz];

int solution = oo;
int sum;
int taken;

//functions
void dfs(int node);

int main(void)
{
	in = fopen("hamilton.in", "rt");
	out = fopen("hamilton.out", "wt");
	
	fscanf(in,"%d%d", &nodes, &edges);
	
	while(edges--)
	{
		fscanf(in,"%d%d%d", &node1, &node2, &cost);
		graph[node1].pb(mp(node2,cost));
	}
	
	taken =1;
	dfs(0);
	
	if(solution!=oo)	
		fprintf(out, "%d", solution);
	else
		fprintf(out,"Nu exista solutie");
	
	fclose (in);
	fclose(out);
	return 0;	
}


void dfs(int node)
{
	viz[node] = true;
	if(taken == nodes)
	{
		//viz[node] = false;
		vector<pii> :: iterator it2, end2=graph[node].end();
		for( it2=graph[node].begin(); it2!=end2; ++it2)
			if(it2->first == 0)
			{
				sum+=it2->second;
				if(sum < solution)
					solution = sum;
				sum-=it2->second;			
				break;
			}
	}
	
	vector<pii> :: iterator it, end=graph[node].end();
	for( it=graph[node].begin(); it!=end; ++it)
	{
		if(!viz[it->first])
		{
			sum+=it->second;
			taken++;
			dfs(it->first);
			viz[it->first] = false;
			sum-=it->second;
			taken--;
		}
		
	}
}