// acest program a fost facut in incinta Colegiului National de Informatica "Tudor Vianu"
#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int NMAX = 18;
const int INF = 1e9;
int n, m;
int cost[NMAX + 1][NMAX + 1];
int dp[(1 << NMAX)][NMAX + 1];
int DP(int mask, int v) {
if(dp[mask][v] != -1) {
return dp[mask][v];
}
dp[mask][v] = INF;
for(int u = 0; u < n; u++) {
if(cost[u][v] && (mask & (1 << u))) {
dp[mask][v] = min(dp[mask][v], DP(mask ^ (1 << v), u) + cost[u][v]);
}
}
return dp[mask][v];
}
int main() {
ios_base :: sync_with_stdio(0); fin.tie(0); fout.tie(0);
fin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v, c;
fin >> u >> v >> c;
cost[u][v] = c;
}
memset(dp, -1, sizeof(dp));
dp[1][0] = 0;
int ans = INF;
for(int i = 0; i < n; i++) {
if(cost[i][0]) {
ans = min(ans, DP((1 << n) - 1, i) + cost[i][0]);
}
}
if(ans == INF) {
fout << "Nu exista solutie!\n";
} else {
fout << ans << '\n';
}
fin.close();
fout.close();
return 0;
}