# include <algorithm>
# include <cstdio>
# include <cstring>
# include <vector>
using namespace std;

const char *FIN = "hamilton.in", *FOU = "hamilton.out";
const int MAX_N = 20, MAX_X = (1 << 18) + 5, oo = 0x3f3f3f3f;

int N, M, sol, C[MAX_N][MAX_N], dp[MAX_X][MAX_N];
vector <int> G[MAX_N];

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d", &N, &M);
    memset (C, 0x3f, sizeof (C)), memset (dp, 0x3f, sizeof (dp));
    for (int i = 1, x, y, z; i <= M; ++i) {
        scanf ("%d %d %d", &x, &y, &z);
        G[y].push_back (x), C[x][y] = z;
    }
    dp[1][0] = 0;
    for (int i = 0; i < 1 << N; ++i)
        for (int j = 0; j < N; ++j)
            if (i & 1 << j)
                for (vector <int> :: iterator it = G[j].begin (); it != G[j].end (); ++it)
                    if (i & 1 << *it)
                        dp[i][j] = min (dp[i][j], dp[i ^ (1 << j)][*it] + C[*it][j]);
    int sol = oo;
    for (vector <int> :: iterator it = G[0].begin (); it != G[0].end (); ++it)
        sol = min (sol, dp[(1 << N) - 1][*it] + C[*it][0]);
    if (sol == oo) fprintf (fopen (FOU, "w"), "Nu exista solutie");
    else fprintf (fopen (FOU, "w"), "%d", sol);
}