#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

int n, m, c, i, x, y, cost[20][20], dp[1 << 18][20], bitmask, nod, cm, j;
vector < int > g[20];
int oo = 1000000000;

int main()
{
   fin >> n >> m;
   for (i = 0; i <= n; i++)
   {
       for (j = 0; j <= n; j++)
        cost[i][j] = oo;
   }

   for (i = 1; i <= m; i++)
   {
       fin >> x >> y >> c;
       g[x].push_back (y);
       cost[x][y] = c;
   }



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

   dp[1][0] = 0;

    for (bitmask = 0; bitmask < (1 << n); bitmask++)
    {
        for (nod = 0; nod < n; nod++)
        {
            if ((bitmask & (1 << nod)) != 0)
            {
                for (auto it : g[nod])
                {
                    if ((bitmask & (1 << it)) == 0)
                    {
                        dp[bitmask | (1 << it)][it] = min (dp[bitmask | (1 << it)][it], dp[bitmask][nod] + cost[nod][it]);
                    }
                }
            }
        }
    }

    cm = oo;

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

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

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