#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize ("O1")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree <long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update>
#define lsb(x)(x & (-x))

const int max_size = 18, max_c = (1 << 18) + 2, INF = 1e9 + 2;

int cost[max_size][max_size], dp[max_c][max_size];

void solve ()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cost[i][j] = INF;
        }
    }
    for (int i = 1; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            dp[i][j] = INF;
        }
    }
    while (m--)
    {
        int x, y, c;
        cin >> x >> y >> c;
        cost[x][y] = c;
    }
    dp[1][0] = 0;
    for (int i = 1; i < (1 << n); i++)
    {
        for (int j = 0; j < n; j++)
        {
            if ((i & (1 << j)) != 0)
            {
                for (int k = 0; k < n; k++)
                {
                    if ((i & (1 << k)) == 0)
                    {
                        dp[i ^ (1 << k)][k] = min(dp[i][j] + cost[j][k], dp[i ^ (1 << k)][k]);
                    }
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < n; i++)
    {
        ans = min(ans, dp[(1 << n) - 1][i] + cost[i][0]);
    }
    if (ans == INF)
    {
        cout << "Nu exista solutie";
    }
    else
    {
        cout << ans;
    }
    cout << '\n';
}

signed main ()
{
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long tt;
    //cin >> tt;
    tt = 1;
    while (tt--)
    {
        solve();
    }
    return 0;
}