#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define BIT(x) (1<<(x))

using namespace std;

int mat[BIT(18)][18];
int cost[18][18];
int n, m;

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    scanf("%d%d", &n, &m);
    int a, b, c;
    memset(mat, 0x3f, sizeof(mat));
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        cost[a][b] = c;
    }
    mat[1][0] = 0;
    int i, j, k;
    for(i = 3; i < BIT(n); i += 2)
    {
        for(j = 1; j < n; j++)
        {
            for(k = 0; k < n; k++)
            {
                if(i & BIT(k) && cost[k][j])
                {
                    mat[i][j] = min(mat[i][j], mat[i ^ BIT(j)][k] + cost[k][j]);
                }
            }
        }
    }
    int rez = 0x3f3f3f3f;
    for(i = 1; i < n; i++)
    {
        if(!cost[i][0])
            continue;
        rez = min(rez, mat[BIT(n) - 1][i] + cost[i][0]);
    }
    if(rez == 0x3f3f3f3f)
        printf("Nu exista solutie");
    else printf("%d", rez);
    return 0;
}