#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 18
#define inf 0x3fffffff

using namespace std;

int memo[1<<MAXN][MAXN];
int n, m, a[MAXN][MAXN];

void citire()
{
    scanf("%d %d", &n, &m);
    int x, y, c;
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        a[x][y] = c;
    }
}

int solve(int nod, int viz)
{
    if (memo[viz][nod]) return memo[viz][nod];
    int cost = inf;
    if (viz == (1<<nod)+1)
        cost = a[0][nod] ? a[0][nod] : inf;
    else
        for (int i = 1; i < n; i++)
            if (a[i][nod] > 0 && ((viz>>i) & 1))
                cost = min(cost, a[i][nod] + solve(i, viz-(1<<nod)));
    memo[viz][nod] = cost;
    return cost;
}

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

    citire();

    int cost = inf;
        for (int i = 1; i < n; i++)
            if (a[i][0] > 0)
                cost = min(cost, a[i][0] + solve(i, (1<<n)-1));

    if (cost == inf)
        printf("Nu exista solutie");
    else
        printf("%d", cost);

    return 0;
}