#include <cstdio>
#include <cstring>

#include <vector>

using namespace std;

const int MAXN = 19;
const int MAXX = (1 << 18);
const int INF = 0x3f3f3f3f;

int N;
bool edge[MAXN][MAXN];
int cost[MAXN][MAXN];

int dp[MAXN][MAXX];

int doit(int i, int s)
{
    s ^= (1 << i);

    if (s == 0) {
        if (edge[N - 1][i])
            return cost[N - 1][i];
        return INF;
    }
    if (dp[i][s] < INF / 2)
        return dp[i][s];

    for (int j = 0; j < N; ++j) {
        if ((s & (1 << j)) != 0)
            if (edge[j][i])
                dp[i][s] = min(dp[i][s], doit(j, s) + cost[j][i]);
    }

    return dp[i][s];
}

int main()
{
    int M;
    scanf("%d %d", &N, &M);

    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < M; ++i) {
        int x, y, cst;
        scanf("%d %d %d", &x, &y, &cst);
        edge[x][y] = true;
        cost[x][y] = cst;
    }

    int sol = doit(N - 1, (1 << N) - 1);
    if (sol < INF / 2)
        printf("%d\n", sol);
    else
        printf("Nu exista solutie\n");

    return 0;
}