#include <bits/stdc++.h>

using namespace std;

const int MAXN = 18;
const int INF = 0x3f3f3f3f;

int dp[MAXN][1 << MAXN], adj[MAXN][MAXN];

int main()
{
    int n, m;
    ifstream fin("hamilton.in");
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
      int x, y, c;
      fin >> x >> y >> c;
      adj[x][y] = c;
    }
    fin.close();
    memset(dp, INF, sizeof dp);
    for (int conf = 0; conf < (1 << n); ++conf)
      for (int lst = 0; lst < n; ++lst)
        if (conf & (conf - 1)) {
          if (conf & (1 << lst))
            for (int prv = 0; prv < n; ++prv)
              if ((conf & (1 << prv)) && adj[prv][lst])
                dp[lst][conf] = min(dp[lst][conf], dp[prv][conf ^ (1 << lst)] + adj[prv][lst]);
        } else
          dp[lst][conf] = 0;
    int ans = INF;
    for (int i = 1; i < n; ++i)
      if (adj[i][0])
        ans = min(ans, dp[i][(1 << n) - 1] + adj[i][0]);
    ofstream fout("hamilton.out");
    if (ans == INF)
      fout << "Nu exista solutie\n";
    else
      fout << ans << '\n';
    fout.close();
    return 0;
}