#include<iostream>
#include<deque>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

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

const int mx = 18;
const int inf =  2e9;

int n,m;
int cost[mx][mx];
int memo[1<<mx][mx];
vector<int> g[mx];

void read(){
	in>>n>>m;
	int a,b,c;

	for(int i=0;i<m;i++){
		in>>a>>b>>c;
		cost[a][b]=c;
		// Reversed edge.
		g[b].push_back(a);
	}
}

// dp[nodes][last] - the minimum cost of a path that starts at 0, connects all nodes in the bitmask and ends at last.
int dp(int nodes, int last){
	if(memo[nodes][last]!=-1){
		return memo[nodes][last];
	}
	if(nodes==1){
		return 0;
	}

	int result = inf;
	// Get the nodes with an edge to the last node.
	for(int k:g[last]){
		if(nodes & (1<<k)){ // if k is in the path.
			if(k==0 && (nodes ^ (1<<last))!=1) continue;

			int c = dp(nodes ^ (1<<last), k) + cost[k][last];
			result = min(result,c);
		}
	}
	memo[nodes][last] = result;
	return result;
}


void solve(){
	for(int i=0;i<1<<mx;i++){
		for(int k=0;k<mx;k++){
			memo[i][k] =-1;
		}
	}

	int result = inf;
	int all = (1<<n) - 1;

	for(int k:g[0]){
		result = min(result,dp(all,k) + cost[k][0]);
	}
	out<<result;
}


int main(){
	read();
	solve();

	return 0;
}