#include <fstream>
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

class hamilton_solver{
	vector<vector<int> > v;
	vector<vector<pair<int, int> > > transpusa;
public:
	int cost_pentru(const int poz, const int cod){
		if(v[cod][poz] == -1){
			v[cod][poz] = 1<<30;
			for(const auto x : transpusa[poz]){
				if((cod>>x.first)&1){
					v[cod][poz] = min(v[cod][poz],
						cost_pentru(x.first, cod ^ (1<<x.first)) + x.second); } } }
		return v[cod][poz]; }
	int important(){
		return cost_pentru(0, (1<<(transpusa.size()))-1); }

	friend ifstream& operator>>(ifstream& lhs, hamilton_solver& rhs); };

ifstream& operator>>(ifstream& lhs, hamilton_solver& rhs){
	int n, m;
	lhs >> n >> m;
	rhs.v.resize(1<<n, vector<int>(n, -1));
	rhs.v[0][0] = 0;
	rhs.transpusa.resize(n);
	for(int i = 0, a, b, c; i < m; ++i){
		// IN SFARSIT, O PROBLEMA IN CARE SE INDEXEAZA DE LA 0 \0u0/
		lhs >> a >> b >> c;
		rhs.transpusa[b].emplace_back(a, c); }
	return lhs; }

int main(){
	ifstream f("hamilton.in");
	ofstream g("hamilton.out");
	hamilton_solver hs;
	f >> hs;
	g << hs.important();
	return 0; }