#include <fstream>
#include <vector>

#define oo 0x3f3f3f3f
#define Nmax 19

using namespace std;

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

int dp[(1 << Nmax)][Nmax], cost[Nmax][Nmax];
vector < int > G[Nmax];
vector < int > :: iterator it;
int n, m, x, y, c, i, j, bitmask, nod, conf, rasp;

int main()
{
    fin >> n >> m;

    for (i = 0; i < n; i ++)
    {
        for (j = 0; j < n; j ++)
            cost[i][j] = oo;
    }
    for (i = 0; i < (1 << n); i ++)
    {
        for (j = 0; j < n; j ++)
            dp[i][j] = oo;
    }

    while (fin >> x >> y >> c)
    {
        G[x].push_back(y);
        cost[x][y] = c;
    }

    dp[1][0] = 0;

    for (bitmask = 0; bitmask < (1 << n); bitmask ++)
    {
        for (nod = 0; nod < n; nod ++)
        {
            if (bitmask & (1 << nod) != 0)
            {
                for (it = G[nod].begin(); it != G[nod].end(); it ++)
                {
                    if ((bitmask & (1 << (*it))) == 0)
                    {
                        conf = bitmask | (1 << (*it));
                        dp[conf][*it] = min (dp[conf][*it], dp[bitmask][nod] + cost[nod][*it]);
                    }
                }
            }
        }
    }

    rasp = oo;
    for (i = 0; i < n; i ++)
    {
        if (cost[i][0] != oo)
            rasp = min (dp[(1 << n) - 1][i] + cost[i][0], rasp);
    }

    if (rasp == oo)
        fout << "Nu exista solutie";
    else
        fout << rasp;


    fin.close();
    fout.close();
    return 0;
}