#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, x, y, c, C[18][18], sol[18][1 << 18], i, N, mask, j, ans, Mask;
int main() {
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (; m; m--) {
        scanf("%d%d%d", &x, &y, &c);
        C[x][y] = c;
    }
    for (i = 0; i < n - 1; i++)
        sol[i][1 << i] = C[n - 1][i];
    N = (1 << (n - 1)) - 1;
    for (mask = 1; mask <= N; mask++)
        for (i = 0; i < n - 1; i++) {
            if (sol[i][mask]) {
                for (j = 0; j < n - 1; j++) {
                    if (!(mask & (1 << j)) && C[i][j]) {
                        Mask = mask | (1 << j);
                        if (sol[j][Mask])
                            sol[j][Mask] = min(sol[j][Mask], C[i][j] + sol[i][mask]);
                        else
                            sol[j][Mask] = C[i][j] + sol[i][mask];
                    }
                }
            }
        }
    ans = 18000010;
    for (i = 0; i < n - 1; i++)
        if (sol[i][N] && C[i][n - 1])
            ans = min(ans, (sol[i][N] + C[i][n - 1]));
    if (ans == 18000010)
        printf("Nu exista solutie\n");
    else
        printf("%d\n", ans);
    return 0;
}