#include <fstream>
#include <vector>

using namespace std;

ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");

const int INF = 1e9;
const int N = 18;
int dp[(1 << N) + 1][N], a[N + 1][N + 1];

vector <int> gback[N + 1];

int n, m, x, y, cost;

int main()
{
    for (cin >> n >> m; m && cin >> x >> y >> cost; --m)
        gback[y].push_back(x), a[x][y] = cost;
    int m = (1 << n);
    for (int i = 0; i <= m; ++i)
        for(int j = 0; j < n; ++j)
            dp[i][j] = INF;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (!a[i][j])
                a[i][j] = INF;
    dp[1][0] = 0;
    for (int mask = 3; mask < m; mask += 2)
        for (int i = 1; i < n; ++i)
            if (mask & (1 << i))
                for (auto it : gback[i])
                    dp[mask][i] = min(dp[mask ^ (1 << i)][it] + a[it][i], dp[mask][i]);
    int rasp = INF;
    for(int i = 1; i < n; ++i)
        rasp = min (rasp, dp[(1 << n) - 1][i] + a[i][0]);
    if (rasp == INF)
        cout << "Nu exista solutie\n";
    else
        cout << rasp << '\n';
    return 0;
}