#include <cstdio>
#include <climits>
#include <vector>
using namespace std;
const int inf = 1000000;
int dp[262150][50];
int costuri[50][50];
vector<int> vecini[50];
int n, m;
void citire(){
scanf("%d %d", &n, &m);
int tmp1, tmp2, tmp3;
for(int i = 0; i < m; i++){
scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
vecini[tmp1].push_back(tmp2);
// vecini[tmp2].push_back(tmp1);
costuri[tmp1][tmp2] = tmp3;
// costuri[tmp2][tmp1] = tmp3;
}
for(int i = 0; i < (1 << n); i++){
for(int j = 0; j < n; j++){
dp[i][j] = inf;
}
}
}
void solve(){
dp[1][0] = 0;
for(int i = 0; i < n; i++){
dp[(1 << i)][i] = 0;
}
for(int i = 0; i < (1 << n); i++){
for(int j = 0; j < n; j++){
if((i | (1 << j)) == i){
int l = vecini[j].size();
for(int k = 0; k < l; k++){
if((i | (1 << vecini[j][k])) == i){
dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][vecini[j][k]] + costuri[vecini[j][k]][j]);
}
}
}
}
}
int sol = inf;
int l = vecini[0].size();
for(int i = 0; i < l; i++){
int x = dp[(1 << n) - 1][vecini[0][i]] + costuri[0][vecini[0][i]];
if(x < sol){
sol = x;
}
}
if(sol == inf){
printf("Nu exista solutie");
}
else{
printf("%d\n", sol);
}
}
int main()
{
freopen("hamilton.in", "r", stdin);
freopen("hamilton.out", "w", stdout);
citire();
solve();
return 0;
}