#include <fstream>
#include <vector>
#include <climits>
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int DIM = 19;

int n, m, x, y, c;
int dp[(1 << DIM)][DIM];
int mat[DIM][DIM];

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        mat[x][y] = c;
    }

    const int MAX_STATE = (1 << n) - 1;
    for (int state = 1; state <= MAX_STATE; state++)
        for (int i = 0; i < n; i++)
            dp[state][i] = INT_MAX;

    dp[1][0] = 0;
    for (int state = 1; state <= MAX_STATE; state++) {
        for (int node = 0; node < n; node++) {
            if (dp[state][node] != INT_MAX) {
                for (int adjNode = 0; adjNode < n; adjNode++) {
                    if (mat[node][adjNode] != 0 && ((state >> adjNode) & 1) == 0) {
                        int newState = state + (1 << adjNode);
                        int adjCost = mat[node][adjNode];
                        dp[newState][adjNode] = min(dp[newState][adjNode], dp[state][node] + adjCost);
                    }
                }
            }
        }
    }

    int sol = INT_MAX;
    for (int i = 1; i < n; i++) {
        if (mat[i][0] != 0)
            sol = min(sol, dp[MAX_STATE][i] + mat[i][0]);
    }

    if (sol == INT_MAX) {
        fout << "Nu exista solutie";
        return 0;
    }
    fout << sol;

    return 0;
}