#include <fstream>
#include <vector>
#include <climits>

using namespace std;

ifstream fin  ("hamilton.in");
ofstream fout ("hamilton.out");

int n, m, i, x, y, c, j, staremax, sol, k, vecin, cost;
int v[20];
int d[20][(1<<18)];

vector <pair<int, int> > L[20];

int main(){
    fin >> n >> m;
    for (i=1; i<=n; i++){
        v[i] = INT_MAX;
    }
    for (i=1; i<=m; i++){
        fin >> x >> y >> c;
        L[x].push_back({y, c});
        if (y == 0)
            v[x] = c;
    }
    for (i=0; i<18; i++){
        for (j=0; j<(1<<18); j++)
            d[i][j] = INT_MAX;
    }
    staremax = (1<<n);
    d[0][1] = 0;
    sol = INT_MAX;
    for (i=1; i<staremax; i+=2){
        for (j=0; j<n; j++){
            if (d[j][i] != INT_MAX){
                for (k=0; k<L[j].size(); k++){
                    vecin = L[j][k].first, cost = L[j][k].second;
                    if (!(i&(1<<vecin))){
                        d[vecin][i+(1<<vecin)] = min (d[vecin][i+(1<<vecin)], d[j][i] + cost);
                    }
                }
            }
        }
    }
    for (i=1; i<n; i++){
        if (d[i][(1<<n)-1] != INT_MAX && v[i] != INT_MAX){
            sol = min (sol, d[i][(1<<n)-1] + v[i]);
        }
    }
    if (sol != INT_MAX)
        fout << sol;
    else
        fout << "Nu exista solutie";
    return 0;
}