#include <stdio.h>
#include <vector>
#define MAXN 25
#define INF 0x3fffffff
#define MIN(a, b) (((a) < (b))?(a):(b))
using namespace std;

int n, m, cost[MAXN][MAXN], dp[1 << 18][MAXN];
int x, y, c;
vector<int> GT[MAXN];

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

    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d %d %d", &x, &y, &c);
        cost[x][y] = c;
        GT[y].push_back(x);
    }

    for(int i = 0; i < n; i++) dp[0][i] = INF;
    dp[0][n - 1] = 0;

    for(int mask = 1; mask < (1 << (n - 1)); mask++)
        for(int i = 0; i < n; i++) {
            dp[mask][i] = INF;
            if(!(mask & (1 << i))) continue;
            for(auto x: GT[i])
                dp[mask][i] = MIN(dp[mask][i], dp[mask ^ (1 << i)][x] + cost[x][i]);
        }

    int sol = INF;
    for(int i = 0; i < n - 1; i++)
        if(cost[i][n - 1])
            sol = MIN(sol, dp[(1 << (n - 1)) - 1][i] + cost[i][n - 1]);

    if(sol == INF) printf("Nu exista solutie\n");
    else printf("%d\n", sol);

    return 0;
}