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

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

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<N; ++i)
        for (j=0; j<N; ++j)
            cost[i][j] = mult;

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

    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 arc k->i}
            if (j & 1<<i)
                for (k=0; k<smeq[i].size(); ++k)
                    if (j&(1<<smeq[i][k]))
                        C[i][j] = min(C[i][j], C[smeq[i][k]][j^(1<<i)] + cost[smeq[i][k]][i]);

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

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

    return 0;
}