#include <bits/stdc++.h>
using namespace std;

const int INF=1e9;
const int NMAX=18;
int dp[1<<NMAX][NMAX];
int cost_edge[NMAX][NMAX];
bool edge[NMAX][NMAX];

int main() {
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	int N, M;
	cin>>N>>M;
	for(int i=1;i<=M;++i) {
		int a, b, c;
		cin>>a>>b>>c;
		edge[a][b]=true;
		cost_edge[a][b]=c;
	}
	for(int i=0;i<(1<<N);++i) {
		for(int j=0;j<N;++j) {
			dp[i][j]=INF;
		}
	}
	for(int i=0;i<N;++i) {
		dp[(1<<i)][i]=0;
	}
	for(int mask=0;mask<(1<<N);++mask) {
		vector<int> possible;
		for(int node=0;node<N;++node) {
			if(!(mask&(1<<node)))
				possible.push_back(node);
		}
		for(int node=0;node<N;++node) {
			if(!(mask&(1<<node)) || dp[mask][node]==INF) 
				continue;
			for(auto &next_node:possible) {
				if(edge[node][next_node]) {
					dp[mask+(1<<next_node)][next_node]=min(dp[mask+(1<<next_node)][next_node], dp[mask][node]+cost_edge[node][next_node]);
				}
			}
		}
	}

	int MIN=INF;
	for(int i=1;i<N;++i) {
		if(edge[i][0]) {
			MIN=min(MIN, dp[(1<<N)-1][i]+cost_edge[i][0]);
		}
	}
	cout<<MIN<<'\n';
	return 0;
}