// acest program a fost facut in incinta Colegiului National de Informatica "Tudor Vianu"
#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int NMAX = 18;
const int INF = 1e9;

int n, m;
int cost[NMAX + 1][NMAX + 1];
int dp[(1 << NMAX)][NMAX + 1];

int main() {
	ios_base :: sync_with_stdio(0); fin.tie(0); fout.tie(0);
	fin >> n >> m;

  fill(dp[0], dp[(1 << NMAX)], INF);

	for(int i = 1; i <= m; i++) {
		int u, v, c;
		fin >> u >> v >> c;

		cost[u][v] = c;
	}

  int ans = INF;
  dp[1][0] = 0;

  for(int mask = 1; mask < (1 << n); mask++) {
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        if(mask & (1 << i) && cost[j][i]) {
          dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + cost[j][i]);
        }
      }
    }
  }

  for(int i = 0; i < n; i++) {
    if(cost[i][0]) {
      ans = min(ans, dp[(1 << n) - 1][i] + cost[i][0]);
    }
  }

	if(ans == INF) {
		fout << "Nu exista solutie!\n";
	} else {
		fout << ans << '\n';
	}

	fin.close();
	fout.close();
	return 0;
}