#include <fstream>
using namespace std;
ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");
int n, m;
int x, y, c;
int cost[20][20];
int dp[20][1 << 18];
int minn = 1e9;
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cost[i][j] = 1e9;
}
}
for (int i = 1; i <= m; i++)
{
cin >> x >> y >> c;
cost[x][y] = c;
}
for (int mask = 0; mask < (1 << n); mask++)
{
for (int nod = 0; nod < n; nod++)
{
dp[nod][mask] = 1e9;
}
}
dp[0][1] = 0;
for (int mask = 0; mask < (1 << n); mask++)
{
for (int nod = 0; nod < n; nod++)
{
if (mask >> nod & 1)
{
for (int bit = 0; bit < n; bit++)
{
if (mask >> bit & 1 && bit != nod)
{
dp[nod][mask] = min(dp[nod][mask], dp[bit][mask - (1 << nod)] + cost[bit][nod]);
}
}
}
}
}
for (int i = 1; i < n; i++)
{
if (cost[i][0] != 1e9)
minn = min(minn, dp[i][(1 << (n)) - 1] + cost[i][0]);
}
if (minn == 1e9) cout << "Nu exista solutie";
else cout << minn;
return 0;
}