#include <cstdio>
#include <vector>
#define NMAX 20
using namespace std;

int cost[NMAX][NMAX], C[NMAX][1<<NMAX];
int N, M;
const int mult = 1<<30;

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    int i, j, k, a, b, c;
    scanf("%d%d", &N, &M);

    for (i=0; i<M; ++i)
    {
        scanf("%d%d%d", &a, &b, &c);
        cost[a][b] = c;
    }

    for (i=0; i<N; ++i)
        for (j=0; j<(1<<N); ++j)
            C[i][j] = mult;
    C[0][1] = 0;

    for (j=0; j<1<<N; ++j)
        for (i=0; i<N; ++i)
            //C[i][j] = min{C[k][j xor (1<<i)] | k apartine lantului binar j si exista muchie k->i}
            //if (j & 1<<i)
                for (k=0; k<N; ++k)
                    if (cost[k][i] && j&(1<<k))
                        C[i][j] = min(C[i][j], C[k][j^(1<<i)] + cost[k][i]);

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

    if (result == mult) printf("Nu exista solutie.");
    else printf("%d", result);

    return 0;
}