#include <fstream>
#include <vector>
#define INF 1000000000

using namespace std;

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

int n,m,i,j,x,y,c,d[20][(1<<20)];
vector< pair<int, int> > L[20],lista;

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