#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 19,
          XMAX = (1 << 18),
          INF = 1 << 29;

int n, m, nn, cost[NMAX][NMAX],
    c[XMAX][NMAX];
vector<int> G[NMAX];

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

void citire()
{
    int x, y;
    fin >> n >> m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cost[i][j] = INF;
    for(int i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        G[y].push_back(x);
        fin >> cost[x][y];
    }
    nn = (1 << n) - 1;
}

int calcul(int cfg, int j)
{
    if(c[cfg][j] == -1)
    {
        c[cfg][j] = INF;
        for(int &x : G[j])
            if(cfg & (1 << x))
            {
                if(x == 0 && cfg != (1 << j) + 1) continue;
                c[cfg][j] = min(c[cfg][j], calcul(cfg ^ (1 << j), x) + cost[x][j]);
            }
    }
    return c[cfg][j];
}

int main()
{
    int sol = INF;
    citire();
    for(int i = 0; i <= nn; ++i)
        for(int j = 0; j < n; ++j)
            c[i][j] = -1;
    c[1][0] = 0;
    for(int& nod : G[0]) sol = min(sol, calcul(nn, nod) + cost[nod][0]);
    if(sol == INF) fout << "Nu exista solutie";
    else fout << sol;
    return 0;
}