#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int INF = 18000005;
int gr[20][20];
int dp[1 << 18][18];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int nodes, edges;
    cin >> nodes >> edges;

    for (int i = 0; i < nodes; i++) {
        for (int j = 0; j < nodes; j++) {
            gr[i][j] = 0;
        }
    }

    for (int i = 1; i <= edges; i++) {
        int a, b, val;
        cin >> a >> b >> val;
        gr[a][b] = val;
    }

    for (int i = 0; i < (1 << nodes); i++) {
        for (int j = 0; j < nodes; j++) {
            dp[i][j] = INF;
        }
    }

    dp[1][0] = 0;

    for (int mask = 1; mask < (1 << nodes); mask++) {
        for (int i = 0; i < nodes; i++) {
            if (mask & (1 << i)) {
                for (int j = 0; j < nodes; j++) {
                    if (!(mask & (1 << j)) && gr[i][j] != 0) {
                        if (dp[mask][i] != INF) {
                            dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + gr[i][j]);
                        }
                    }
                }
            }
        }
    }

    int MIN = INF;
    for (int i = 0; i < nodes; i++) {
        if (dp[(1 << nodes) - 1][i] != INF && gr[i][0] != 0) {
            MIN = min(MIN, dp[(1 << nodes) - 1][i] + gr[i][0]);
        }
    }

    if (MIN == INF) {
        cout << "Nu exista solutie";
    } else {
        cout << MIN;
    }

    return 0;
}