// Hamilton - infoarena.ro/problema/hamilton
// Ciclu hamiltonian de cost minim, PD pe stari exponentiale: dp[mask][v]
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;            // cost maxim real: 18 * 10^6, deci INF nu se atinge
const int NMAX = 18;

int n, m;
int c[NMAX][NMAX];              // c[x][y] = costul arcului x -> y, INF daca nu exista
int dp[1 << NMAX][NMAX];        // dp[mask][v] = cost minim al unui drum care porneste din 0,
                                // viziteaza exact nodurile din mask si se termina in v

int main() {
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");

    fin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) c[i][j] = INF;
    for (int i = 0; i < m; i++) {
        int x, y, cost;
        fin >> x >> y >> cost;
        c[x][y] = cost;          // graf orientat: arc x -> y
    }

    int full = (1 << n) - 1;
    for (int mask = 0; mask <= full; mask++)
        fill(dp[mask], dp[mask] + n, INF);
    dp[1][0] = 0;                                 // start in nodul 0

    for (int mask = 1; mask <= full; mask += 2)   // bitul 0 mereu setat
        for (int v = 0; v < n; v++) {
            if (!((mask >> v) & 1) || dp[mask][v] == INF) continue;
            for (int u = 0; u < n; u++)
                if (!((mask >> u) & 1) && c[v][u] < INF) {
                    int nou = mask | (1 << u);
                    dp[nou][u] = min(dp[nou][u], dp[mask][v] + c[v][u]);
                }
        }

    int ans = INF;
    for (int v = 1; v < n; v++)                   // ultimul nod v, apoi arcul v -> 0
        if (dp[full][v] < INF && c[v][0] < INF)
            ans = min(ans, dp[full][v] + c[v][0]);

    if (ans == INF) fout << "Nu exista solutie\n";
    else fout << ans << "\n";
    return 0;
}