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

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(mem[a][b] == INF){
		for(auto x : gra[a]){
			if(getbit(b, x.a)){
				mem[a][b] = min(mem[a][b], recur(x.a, setbit(b, x.a, 0))+x.v);
			}
		}
	}
	return mem[a][b];
}

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;
	fout << recur(0, full);
	return 0;
}