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

int cost[NMAX][NMAX], C[superMAX][NMAX];
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<1<<N; ++i)
        for (j=0; j<N; ++j)
            C[i][j] = mult;
    C[1][0] = 0;

    for (i=0; i<1<<N; ++i)
        for (j=0; j<N; ++j)
            if (i & 1<<j)
                for (k=0; k<smeq[j].size(); ++k)
                    if (i&(1<<smeq[j][k]))
                        C[i][j] = min(C[i][j], C[i^(1<<j)][smeq[j][k]] + cost[smeq[j][k]][j]);

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

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

    return 0;
}