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

using namespace std;

int memo[MAXN][1<<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 (viz == 1 && nod == 0) return 0;
    if (memo[nod][viz]) return memo[nod][viz];
    int cost = inf;
    for (int i = 0; i < n; i++)
        if (a[i][nod] > 0 && i != nod && ((viz>>i) & 1))
            cost = min(cost, a[i][nod] + solve(i, viz-(1<<nod)));
    memo[nod][viz] = 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;
}