#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int MAXP = (1 << 18) + 5;
const int MAXN = 20;
const int INF = 1e9;
vector <int> a[MAXN];
int cost[MAXN][MAXN];
int ans[MAXP][MAXN];
void initializare(int n){
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cost[i][j] = INF;
    for(int i = 0; i < (1 << n); ++i)
        for(int j = 0; j < n; ++j)
            ans[i][j] = INF;
}
int main(){
    int n, m, minim = INF;
    fin >> n >> m;
    initializare(n);
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        fin >> x >> y >> c;
        a[y].push_back(x);
        cost[x][y] = c;
    }
    ans[1][0]= 0;
    for(int i = 0; i < (1 << n); ++i)
        for(int j = 0; j < n ;++j)
            if(i & (1 << j))
                for(int k = 0; k < a[j].size(); ++k)
                    if(i & ( 1 << a[j][k] ))
                        ans[i][j] = min(ans[i][j], ans[i ^ (1 << j)][a[j][k]] + cost[a[j][k]][j]);
    for(int i = 0; i < a[0].size(); ++i){
        minim = min(minim , ans[(1 << n) - 1][a[0][i]] + cost[a[0][i]][0]);
    }
    if(minim == INF) fout << "Nu exista solutie";
    else fout << minim;
    return 0;
}