#include <fstream>

using namespace std;

ifstream cin ("hamilton.in");
ofstream cout ("hamilton.out");

const int inf = 1e9;

int n, m, graf[20][20], dp[1 << 18][20];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            graf[i][j] = inf;
        }
    }

    for (int i = 0; i < (1 << 18); i++) {
        for (int j = 0; j < 20; j++) {
            dp[i][j] = inf;
        }
    }

    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        graf[x][y] = w;
    }

    dp[1][0] = 0;

    for (int s = 2; s < (1 << n); s++) {
        for (int i = 1; i < n; i++) {
            if (s & (1 << i)) {
                for (int k = 0; k < n; k++) {
                    if (s & (1 << k)) {
                        dp[s][i] = min(dp[s][i], dp[s ^ (1 << i)][k] + graf[k][i]);
                    }
                }
            }
        }
    }

    int minim = inf;

    for (int i = 1; i < n; i++) {
        minim = min(minim, dp[(1 << n) - 1][i] + graf[i][0]);
    }

    if (minim == inf) cout << "Nu exista solutie";
    else cout << minim;

    return 0;
}