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

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

vector<pii> graph[sz];

bool viz[sz];

int taken, solution = (1<<30)-1;
int sum, first;

//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));
	}
	
	for(int i=0; i<nodes; ++i)
	{
		taken = 1;
		first = i;
		sum = 0;
		dfs(i);
		for(int j=0; j<nodes; ++j)
			viz[j] = false;
	}
		
	fprintf(out, "%d", solution);
	
	fclose (in);
	fclose(out);
	return 0;	
}


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