#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>
#define vi vector<int>
#define f first
#define s second
#define pb push_back
#define lsh(i) (1 << (i))

using namespace std;

const int oo = 2e8;
int n, m;
vector<vi> dp;
vector<vector<pii>> a;

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    cin >> n >> m;
    a = vector<vector<pii>>(n);
    vector<pii> zero_parents;

    for(int i = 0; i < m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        a[x].pb({y, c});
        if(y == 0)
            zero_parents.pb({x, c});
    }

    dp = vector<vi>(lsh(n), vi(n, oo));
    dp[1][0] = 0;

    for(int mask = 0; mask < lsh(n); ++mask)
        for(int i = 0; i < n; ++i)
            if(mask & lsh(i))
                for(auto [j, c]: a[i])
                    if(!(mask & lsh(j)))
                        if(dp[mask][i] + c < dp[mask | lsh(j)][j])
                            dp[mask | lsh(j)][j] = min(dp[mask | lsh(j)][j], dp[mask][i] + c);

    int ans = oo;

    for(auto [node, c]: zero_parents)
        ans = min(ans, dp[lsh(n) - 1][node] + c);

    (ans == oo) ? cout <<"Nu exista solutie" : cout << ans;

    return 0;

}