#include <stdio.h>

#define inf 0x3f3f3f3f
#define len(x) vecini[x][0]

int n, m, x, y, minc = inf;
int cost[18][18], c[262144][18];

int min(int a, int b)
{
    return a < b ? a : b;
}

int calc(int j, int k)
{
    if(c[j][k] == -1)
    {
        c[j][k] = inf;
        for(int v = 0; v < n; v++)
            if(j & (1 << v) && cost[v][k] != inf)
            {
                if(v == 0 && j != (1 << k) + 1)continue;
                c[j][k] = min(c[j][k], calc(j ^ (1 << k), v) + cost[v][k]);
            }
    }
    return c[j][k];
}

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cost[i][j] = inf;
    for(int i = 0; i < 1 << n; i++)
        for(int j = 0; j < n; j++)
            c[i][j] = -1;
    c[1][0] = 0;
    for(int i = 0; i < m; i++)
    {
        scanf("%d %d", &x, &y);
        scanf("%d", &cost[x][y]);
    }
    for(int i = 1; i < n; i++)
        if(cost[i][0] != inf)
            minc = min(minc, calc((1 << n) - 1, i) + cost[i][0]);
    if(minc == inf)
        printf("Nu exista solutie");
    else
        printf("%d", minc);
}