#include <bits/stdc++.h>

using namespace std;

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

int dp[1 << MAXN][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);
    dp[1][0] = 0;
    for (int conf = 0; conf < (1 << n); ++conf)
      for (int lst = 0; lst < n; ++lst)
        if (conf & (1 << lst))
          for (int prv = 0; prv < n; ++prv)
            if ((conf & (1 << prv)) && adj[prv][lst])
              dp[conf][lst] = min(dp[conf][lst], dp[conf ^ (1 << lst)][prv] + adj[prv][lst]);
    int ans = INF;
    for (int i = 1; i < n; ++i)
      if (adj[i][0])
        ans = min(ans, dp[(1 << n) - 1][i] + adj[i][0]);
    ofstream fout("hamilton.out");
    if (ans == INF)
      fout << "Nu exista solutie\n";
    else
      fout << ans << '\n';
    fout.close();
    return 0;
}