#include <cstdio>
#include <cstring>

#include <vector>

using namespace std;

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

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

vector<int> G[MAXN];

int dp[MAXX][MAXN];

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[s][i] < INF / 2)
        return dp[s][i];

    vector<int>::iterator it;
    for (it = G[i].begin(); it != G[i].end(); ++it)
        if ((s & (1 << (*it))) != 0)
                dp[s][i] = min(dp[s][i], doit(*it, s) + cost[*it][i]);

    return dp[s][i];
}

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

    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);
        cost[x][y] = cst;
        edge[x][y] = true;
        G[y].push_back(x);
    }

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

    return 0;
}