#include <cstdio>
#include <iostream>

using namespace std;

const int N = 18;
const int INF = (int) 1e9;
int n, m;
int cnt[N], who[N][N];
int x, y, c, aux, lsb, i, j, mask, k, upd, k2;
int d[N][N];
int best[(1 << N)][N];
int lg[(1 << N)];
int bits[N], cntb;

int main()
{
        freopen ("hamilton.in", "r", stdin);
        freopen ("hamilton.out", "w", stdout);

        scanf("%d %d", &n, &m);
        for (i = 0; i < m; i++)
        {
                scanf("%d %d %d", &y, &x, &c);
                d[y][x] = c;
                who[x][cnt[x]++] = y;
        }

        for (i = 0; i < N; i++)
                lg[(1 << i)] = i;

        for (mask = 0; mask < (1 << n); mask++)
                for (i = 0; i < n; i++)
                        best[mask][i] = INF;

        best[1][0] = 0;

        for (mask = 2; mask < (1 << n); mask++)
        {
                aux = mask;
                cntb = 0;
                while (aux)
                {
                        lsb = aux & (-aux);
                        aux -= lsb;
                        bits[cntb++] = lg[lsb];
                }
                for (k = 0; k < cntb; k++)
                {
                        i = bits[k];
                        for (k2 = 0; k2 < cntb; k2++)
                                if (k != k2 && d[bits[k2]][i])
                                {
                                        j = bits[k2];
                                        upd = best[mask - (1 << i)][j] + d[j][i];
                                        if (upd < best[mask][i])
                                                best[mask][i] = upd;
                                }
                }
        }

        int ans = INF;
        for (k = 0; k < cnt[0]; k++)
        {
                j = who[0][k];
                upd = best[(1 << n) - 1][j] + d[j][0];
                if (upd < ans)
                        ans = upd;
        }
        if (ans == INF) printf("Nu exista solutie\n"); else
        printf("%d\n", ans);

        return 0;
}