#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m, mat[20][20], d[20][524288], sol = 0x3f3f3f3f, x, y, z;

int main()
{
    int conf, i, nod, j;
    freopen ("hamilton.in", "r", stdin);
    freopen ("hamilton.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(i = 0; i < m; ++i) {
        scanf("%d %d %d", &x, &y, &z);
        mat[x][y] = z;
    }
    for(i = 0; i <= n; ++i)
        for(j = 0; j <= (1 << n) - 1; ++j)
            d[i][j] = 0x3f3f3f3f;
    d[0][1] = 0;
    for(conf = 0; conf < (1 << n); ++conf) {
        for(nod = 0; nod < n; ++nod) {
                if((conf & (1 << nod)) != 0)
                    for(i = 0; i < n; ++i) {
                        if(((conf & (1 << i)) == 0) && mat[nod][i] > 0) {
                            d[i][conf + (1 << i)] = min(d[nod][conf] + mat[nod][i], d[i][conf + (1 << i)]);
                           // cerr << i << ' ' << conf + (1 << i) << ' ' << d[i][conf + (1 << i)] << '\n';
                        }

                    }
        }
    }

    for(i = 0; i < n; ++i)
        if(mat[i][0] > 0)
        if(d[i][(1 << n) - 1] + mat[i][0] < sol) {
            sol = d[i][(1 << n) - 1] + mat[i][0];
           // cerr << d[i][(1 << n - 1)] << ' ';
        }
    if(sol == 0x3f3f3f3f)
        printf("Nu exista solutie");
    else printf("%d", sol);
    return 0;
}