#include <bits/stdc++.h>

#define MAXN    18
#define MAXBITS (1<<MAXN)

int N, M;
int cost[MAXN][MAXN];
inline void addEdge(int u, int v, int w) {
    cost[u][v] = w;
}

int full;
int DP[MAXBITS][MAXN];
void GospersHack(int n, int k) {
    int set = (1<<k)-1;
    int limit = (1<<n);
    while (set < limit) {
        for (int i=0; i<n; ++i)
            if (set&(1<<i))
                for (int j=0; j<n; ++j)
                    if (j!=i && set&(1<<j) && cost[j+1][i+1] && DP[set^(1<<i)][j]) {
                        if (DP[set][i] == 0) DP[set][i] = DP[set^(1<<i)][j] + cost[j+1][i+1];
                        else                 DP[set][i] = std::min(DP[set][i], DP[set^(1<<i)][j] + cost[j+1][i+1]);
                        //std::cout << set << ' ' << i << ' ' << DP[set^(1<<i)][j] + cost[j+1][i+1] << ' ' << DP[set][i] << '\n';
                    }

        int c = set & - set;
        int r = set + c;
        set = (((r ^ set) >> 2) / c) | r;
    }
}
void bitsDP() {
    full = (1<<(N-1))-1;
    for (int i=0; i<N-1; ++i)
        DP[(1<<i)][i] = cost[0][i+1];
    for (int i=2; i<=N-1; ++i)
        GospersHack(N-1, i);
}

#define FILENAME    std::string("hamilton")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int32_t main()
{
    input >> N >> M;
    for (int i=0, u, v, w; i<M; ++i)
        input >> u >> v >> w, addEdge(u, v, w);
    bitsDP();

    int ans = 2e9;
    for (int i=0; i<N-1; ++i)
        if (DP[full][i] > 0 && cost[i+1][0] > 0)
            ans = std::min(ans, DP[full][i] + cost[i+1][0]);
    if (ans == 2e9) output << "Nu exista solutie\n";
    else            output << ans << '\n';

    return 0;
}