#include <cstdio>

#define DIM 20
#define INF (1<<29)
using namespace std;

int N, M, X, Y, Z;
int C[DIM][DIM];
int D[(1<<DIM)][DIM];

template <typename TYPE>
TYPE min (TYPE A, TYPE B) {
    return A < B ? A : B;
}


int main () {

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

    scanf ("%d %d", &N, &M);
    for (int i = 1; i <= M; i ++) {
        scanf ("%d %d %d", &X, &Y, &Z);
        C[X][Y] = Z;
    }

    for (int i = 1; i < (1<<N); i ++)
    for (int j = 0; j < N; j ++)
        D[i][j] = INF;
    D[1][0] = 0;

    for (int i = 1; i < (1<<N); i ++)
    for (int j = 0; j < N; j ++) {

        if (!(i & (1<<j)))
            continue;

        for (int k = 0; k < N; k ++) {

            if (!(!(i & (1<<k)) && C[j][k]))
                continue;

            D[i+(1<<k)][k] = min (D[i+(1<<k)][k], D[i][j] + C[j][k]);
        }
    }

    int MIN = INF;

    for (int i = 1; i < N; i ++)
        if (C[i][0] != 0)
            MIN = min (MIN, D[(1<<N)-1][i] + C[i][0]);

    if (MIN == INF)
        printf ("Nu exista solutie\n");
    else
        printf ("%d\n", MIN);

    fclose (stdin );
    fclose (stdout);

    return 0;
}