#include <bits/stdc++.h>

using namespace std;

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

int n, m, cost[20][20];
int dp[(1 << 18) + 2][20];
vector<int>g[20];

void hamilton() {
  for (int i = 0; i < (1 << n); i++)
		for (int j = 0; j < n; j++)
      dp[i][j] = (1 << 30);
	dp[1][0] = 0;
	for (int mask = 0; mask < (1 << n); mask++)
		for (int i = 0; i < n; i++)
      if (mask & (1 << i))
          for (auto it: g[i])
            if (mask & (1 << it))
              dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][it] + cost[it][i]);
	int ans = (1 << 30);
	for(auto it: g[0])
		ans = min(ans, dp[(1 << n) - 1][it] + cost[it][0]);
  if (ans == (1 << 30))
    fout << "Nu exista solutie";
  else
    fout << ans;
}

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y;
    fin >> x >> y;
    fin >> cost[x][y];
    g[y].push_back(x);
  }
  hamilton();
  return 0;
}