#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 main()
{
    ifstream in("hamilton.in");
    ofstream out("hamilton.out");

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

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

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

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

    for (int mask = 0; mask < (1 << n); mask++)
      for (int nod = 0; nod < n; nod++)
        dp[mask][nod] = INF;
    dp[1][0] = 0;

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

    int sol = INF;

    for (auto& vecin : graf[0])
      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;
}