#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define pii pair<int, int>
#define tpl tuple<int, int, int>
#define oo 0x3f3f3f3f
using namespace std;

const string fn("hamilton");

ifstream in(fn + ".in");
ofstream out(fn + ".out");

#define cin in
#define cout out

const int MAX = 20;

int n, m, cost[25][25];
int dp[20][1 << 18];
vector<int> from, to;

int main()
{
    cin >> n >> m;

    for (int i = 1, x, y, w; i <= m; i++)
    {
        cin >> x >> y >> w;
        cost[x][y] = w;
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!cost[i][j])
                cost[i][j] = oo;
    memset(dp, oo, sizeof(dp));
    for (int i = 0; i < n; i++)
        dp[i][1 << i] = cost[0][i];

    for (int mask = 1; mask < (1 << n) - 1; mask++)
    {
        for (int node = 0; node < n; node++)
            (mask & (1 << node) ? from.eb(node) : to.eb(node));

        for (auto x : from)
            for (auto y : to)
                if (cost[x][y] != oo and dp[x][mask] != oo)
                    dp[y][mask | (1 << y)] = min(dp[y][mask | (1 << y)], dp[x][mask] + cost[x][y]);
        from.clear();
        to.clear();
    }

    if (dp[0][(1 << n) - 1] == oo)
        cout << "Nu exista solutie";
    else
        cout << dp[0][(1 << n) - 1];
    return 0;
}