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

#define REP(i,a) for (int i = 0; i < (a); i++)
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define ROF(i,a,b) for (int i = (a); i >= (b); i--)
#define FOREACH(it,x) for (auto it: (x))
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())
#define pow2(x) (1<<(x))

const int Nmax = 18;
const int inf = (1<<30);

int n,m;
int cost[Nmax][Nmax];
int best[1<<Nmax][Nmax];

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

    fin >> n >> m;
    while (m--) {
        int x,y,c;
        fin >> x >> y >> c;
        cost[x][y] =  c;
    }

    REP(i,pow2(n)) REP(j,n) best[i][j] = inf;
    FOR(i,1,n-1) if (cost[0][i]) {
        best[pow2(i)|1][i] = cost[0][i];
    }

    REP(conf,1<<n) FOR(i,1,n-1)  if (conf & pow2(i)) {
        FOR(j,1,n-1) if (i != j && (pow2(j) & conf) && cost[j][i]) {
            best[conf][i] = min(best[conf][i], best[conf^pow2(i)][j] + cost[j][i]);
        }
    }

    int Min = inf;
    FOR(i,1,n-1) if (cost[i][0]) Min = min(Min,best[(1<<n)-1][i] + cost[i][0]);
    if (Min != inf) fout << Min;
    else fout << "Nu exista solutie";
}