#include <fstream>
#include <vector>
#include <limits.h>

#define NMax 20

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int nodes, edges, n1, n2, c, mark[NMax], dmin = INT_MAX;
vector<int> G[NMax], cost[NMax];

void dfs(int node, int touchedNodes, int mcost)
{
	mark[node] = 1;

	for (vector<int>::iterator itg = G[node].begin(), itc = cost[node].begin(); itg != G[node].end(); itg++, itc++) {

		if (!mark[*itg])
			dfs(*itg, touchedNodes + 1, mcost + *itc);

		if (*itg == 0 && touchedNodes == nodes && mcost + *itc < dmin)
			dmin = mcost + *itc;

	}

	mark[node] = 0;
}

int main()
{
	f >> nodes >> edges;

	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2 >> c;

		G[n1].push_back(n2);
		cost[n1].push_back(c);
	}

	dfs(0, 1, 0);

	g << dmin;

	return 0;
}