#include <iostream>
#include <fstream>
#include <vector>
#include <limits>

using namespace std;
int INF = numeric_limits<int>::max();

class Graph
{
private:
	int n, m;
	vector<vector<pair<int, int>>> adj_list_costs; //A vector with the neighbours of all the nodes and the cost of the edge between them
public:
	Graph(int nodes, int edges);
	void add_edge_cost(int parent, int child, int cost);
	int hamilton();
};
Graph::Graph(int nodes_no, int edges_no) // Initiate the values of the graph
{
	n = nodes_no;
	m = edges_no;
	adj_list_costs.resize(n + 1);
}
void Graph::add_edge_cost(int parent, int child, int cost) // Adding edges and their costs in the adjacency list
{
	adj_list_costs[parent].push_back(make_pair(child, cost));
}
int Graph::hamilton() // Minimum Flow Cost Hamiltonian Cycle
{
	int final_cost = INF; // The final cost of the Hamiltonian Cycle
	int nodes_no = 1 << n;
	int costs[nodes_no][n]; // costs[i][j] of minimal costs between 0 and a node j that
	                        // contains exactly the nodes used in binary representation of i
	for (int i = 0; i < nodes_no; i++)
		for (int j = 0; j < n; j++)
			costs[i][j] = INF;
	costs[1][0] = INF; // Let the cycle begin form the 0, so the cycle with only the node 0 has a cost of 0
	for (int i = 0; i < nodes_no; i++) // i gives the nodes of the chain
		for (int j = 0; j < n; j++)
			if ((1 << j) & i) // Check if the node is a part of the chain described by i's binary representation
				{
                for (int k = 0; k < adj_list_costs[j].size(); k++)  //
                {

                    if (i & (1 << adj_list_costs[j][k].first)) {
                        costs[i][j] = min(costs[i][j], costs[i ^ (1 << j)][adj_list_costs[j][k].first] +
                                                     adj_list_costs[j][k].second);
                    }
                }
            }

    for (int i = 0; i < adj_list_costs[0].size(); ++i)
        final_cost = min(final_cost, costs[nodes_no - 1][adj_list_costs[0][i].first] +
                             adj_list_costs[0][i].second);
	return final_cost;
}
int main()
{
	// Minimum Flow Cost Hamiltonian Cycle - https://www.infoarena.ro/problema/hamilton
	int n, m;
	ifstream in("hamilton.in");
	ofstream out("hamilton.out");
	in >> n >> m;
	Graph g(n, m);
	for (int i = 0; i < n; i++) // Reading each edge with its own cost
	{
		int parent, child, cost;
		in >> parent >> child >> cost;
		g.add_edge_cost(parent, child, cost);
	}
	int final_cost = g.hamilton(); // Check whether there are any Hamiltonian Cycles and return the minimal value found
	if (final_cost != INF)
		out << final_cost;
	else
		out << "Nu exista solutie";
}