#include<cstdio>
#include<algorithm>
using namespace std;
const int NMAX = 20, INF = 0X3f3f3f3f;
int cost[NMAX + 2][NMAX + 2], d[NMAX][1 << NMAX];
int mask, n, m;
int hamilton(int nod, int mask)
{
    if(d[nod][mask] != 0)
        return d[nod][mask];
    if(mask == (1 << n) - 1)
    {
        if(cost[nod][0])
            d[nod][mask] = cost[nod][0];
        else
            d[nod][mask] = INF;
    }
    else
    {
        int min_cost = INF;
        for(int i = 1; i < n; i++)
            if(cost[nod][i] &&  !(mask & (1<<i)))
                min_cost = min(min_cost, hamilton(i, mask | (1<<i)) + cost[nod][i]);

        d[nod][mask] = min_cost;
    }
    return d[nod][mask];

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

    int i, x, y, c, nod;
    scanf("%d%d", &n, &m);
    for(i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &x, &y, &c);
        cost[x][y] = c;
    }
    mask = 1;
    nod = 0;
    int sol = hamilton(nod, mask);
    if(sol == INF)
        printf("Nu exista solutie");
    else
        printf("%d\n", sol);
    return 0;
}