#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 18;
const int INF = 18000001;

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

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

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

    dp[bitMask][nod] = INF;

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

    return dp[bitMask][nod];
}

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

    for (int i = 0; i < (1 << NMAX); i++)
      for (int j = 0; j < NMAX; j++)
        dp[i][j] = -1;
    dp[1][0] = 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((1 << n) - 1, vecin.first);

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

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

    return 0;
}