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

const int INF = 1e9;
 
int Hamilton(const vector<vector<int>>& cost) {
	int n = cost.size();
	vector<vector<int>> dp(n, vector<int> ((1 << n), INF));
	dp[0][1] = 0;
 
	for(int mask = 3; mask < (1 << n); mask += 2)
		for(int u = 0; u < n; u++)
			if(mask & (1 << u))
				for(int v = 0; v < n; v++)
					if(mask & (1 << v))
						dp[u][mask] = min(dp[u][mask], dp[v][mask ^ (1 << u)] + cost[v][u]);

	int ans = INF;
	for(int i = 0; i < n; i++)
		ans = min(ans, dp[i][(1 << n) - 1] + cost[i][0]);
 
	return (ans == INF ? -1 : ans);
}
 
int main() {
	ifstream cin("hamilton.in");
	ofstream cout("hamilton.out");
	
	int n, m; 
	cin >> n >> m;
	vector<vector<int>> cost(n, vector<int>(n, INF));
	for (int i = 0; i < m; i++) {
		int a, b, c; 
		cin >> a >> b >> c;
		cost[a][b] = c;
	}
 
	int ans = Hamilton(cost);
	if (ans == -1) 
		cout << "Nu exista solutie\n";
	else
		cout << ans << "\n";
 
	return 0;
}