#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 18;
const int INF = 18000002;

int dp[NMAX][1 << NMAX];

vector<pair<int, int>> graf[NMAX];

int calcLant(int nod, int bitMask)
{
    if (dp[nod][bitMask] != INF)
        return dp[nod][bitMask];

    for (auto& vecin : graf[nod])
        if ((bitMask & (1 << vecin.first)) != 0)
            dp[nod][bitMask] = min(dp[nod][bitMask], calcLant(vecin.first, bitMask - (1 << nod)) + vecin.second);

    if (dp[nod][bitMask] == INF)
      dp[nod][bitMask]--;

    return dp[nod][bitMask];
}

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

    for (int i = 0; i < NMAX; i++)
      for (int j = 0; j < (1 << NMAX); j++)
          dp[i][j] = INF;
    dp[0][1] = 0;

    int n, m;
    in >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;

        graf[x].emplace_back(make_pair(y, c));
    }

    if (n == 1)
    {
      out << 0 << '\n';
      return 0;
    }

    int sol = INF;

    for (auto& vecin : graf[0])
    {
      calcLant(vecin.first, (1 << n) - 1);

      sol = min(sol, dp[vecin.first][(1 << n) - 1] + vecin.second);
    }

    if (sol == INF)
        out << "Nu exista solutie" << '\n';
    else
        out << sol << '\n';

    return 0;
}