#include <bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b)
{
    int ans = uniform_int_distribution<int>(a, b)(rng);
    return ans;
}
#define fastio std::ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define test " test "
#define yes "YES"
#define no "NO"
#define bn '\n'
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
//#define int long long
#define deb(a) cout << #a << "=" << (a) << bn
#define deb2(a, b) cout << #a << "=" << (a) << " " << #b << "=" << b << bn
#define readV(v, n)             \
    for (int i = 0; i < n; i++) \
        cin >> v[i];
#define printV(v)    \
    for (auto i : v) \
        cout << i << " ";
#define FILES                           \
    freopen("hamilton.in", "r", stdin); \
    freopen("hamilton.out", "w", stdout);
const int mod = 1e9 + 7;
int maxi = INT_MIN, mini = INT_MAX;
int n, m;
int Cost[20][20];
vector<int> adj[20];
int dp[1 << 18][20];
int ans = 1e9;

int x, y;
int func(int path, int last)
{
    if (dp[path][last] == -1)
    {
        dp[path][last] = 1e9;

        for (auto p : adj[last])
            if (path & 1 << p)
                dp[path][last] = min(dp[path][last], func(path ^ (1 << last), p) + Cost[p][last]);
    }

    return dp[path][last];
}
void solve()
{
    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;
        cin >> Cost[x][y];
        adj[y].push_back(x);
    }
    memset(dp, -1, sizeof(dp));
    dp[1][0] = 0;

     for (auto p : adj[0])
        ans = min(ans, func((1 << n) - 1, p) + Cost[p][0]);

    if (ans == 1e9)
        cout << "Nu exista solutie" << bn;
    else
        cout << ans;
}
signed main()
{
    fastio;
    FILES;
    int __t = 1;
    // cin >> __t;
    while (__t--)
        solve();

    return 0;
}