#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int INF = 0x3f3f3f3f;

struct muc{
	int a, v;
};

int n, m;
vector<muc> gra[20];

int mem[20][300041];

void nuke(){
	for(int i = 0; i < 20; ++i){
		for(int j = 1; j < 300000; ++j){
			mem[i][j] = INF;
		}
	}
}

int setbit(int a, int b, bool v){
	return (a & ~(1<<b)) | (v<<b);
}

bool getbit(int a, int b){
	return (a>>b)&0b1;
}

int recur(int a, int b){
	if(b == 1<<a){
		mem[a][b] = 0;
	}else if(mem[a][b] == INF){
		int nb = setbit(b, a, 0);
		for(auto x : gra[a]){
			if(getbit(b, x.a)){
				mem[a][b] = min(mem[a][b], recur(x.a, nb)+x.v);
			}
		}
	}
	return mem[a][b];
}

muc gime(int a){
	for(auto x : gra[0]){
		if(x.a == a){
			return x;
		}
	}
	return {-1,0};
}

int main(){
	nuke();
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a;
		muc x;
		fin >> x.a >> a >> x.v;
		gra[a].push_back(x);
	}
	int mini = INF;
	int full = (1<<n) - 1;
	for(int i = 1; i < n; ++i){
		muc x = gime(i);
		if(x.a == i){
			mini = min(mini, recur(i, full)+x.v);
		}
	}
	fout << mini;
	return 0;
}