#include <cstdio>
#include <algorithm>
#include <vector>

#define f first
#define s second
#define pii pair <int, int>

using namespace std;

vector <int> v[32];
int dp[300000][20], c[32][32];

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

    int n, m;
    scanf ("%d %d", &n, &m);

    for (int i = 0; i <= 20; ++i)
        for (int j = 0; j <= 20; ++j)
            c[i][j] = 1000000000;

    for (int i = 1; i <= m; ++i)
    {
        int x, y, cost;
        scanf ("%d %d %d", &x, &y, &cost);

        v[x].push_back (y);
        c[x][y] = cost;
    }

    for (int i = 0; i <= (1 << n); ++i)
        for (int j = 0; j <= n; ++j)
            dp[i][j] = 1000000000;

    dp[1][0] = 0;

    for (int i = 1; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j)
        {
            if (dp[i][j] == 1000000000) continue;

            for (auto &it : v[j])
            {
                int h = it;
                if ((1 << h) & i) continue;

                int neww = (i | (1 << h));
                dp[neww][h] = min (dp[neww][h], dp[i][j] + c[j][h]);
                ++h;
            }
        }

    int neww = (1 << n) - 1, mi = 1000000000;
    for (int j = 0; j < n; ++j)
        mi = min (mi, dp[neww][j] + c[j][0]);

    if (mi == 1000000000) printf ("Nu exista solutie\n");
    else printf ("%d\n", mi);

    return 0;
}