#include <iostream>
#include <vector>
#include <climits>
#include <fstream>

using namespace std;

const int MAXN = 18;
const int INF = INT_MAX / 2;

int N, M;
int cost[MAXN][MAXN];
int dp[1 << MAXN][MAXN];

int main() {
    ifstream infile("hamilton.in");
    ofstream outfile("hamilton.out");

    infile >> N >> M;

    // Inițializarea matricei de costuri
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cost[i][j] = INF;
        }
    }

    for (int i = 0; i < M; i++) {
        int u, v, c;
        infile >> u >> v >> c;
        cost[u][v] = c;
    }

    // Inițializarea tabelului dp
    for (int mask = 0; mask < (1 << N); mask++) {
        for (int i = 0; i < N; i++) {
            dp[mask][i] = INF;
        }
    }

    // Condiția inițială: costul de a ajunge la orice nod de start este 0
    for (int i = 0; i < N; i++) {
        dp[1 << i][i] = 0;
    }

    // Calculul dp
    for (int mask = 0; mask < (1 << N); mask++) {
        for (int u = 0; u < N; u++) {
            if (mask & (1 << u)) {
                for (int v = 0; v < N; v++) {
                    if (!(mask & (1 << v)) && cost[u][v] < INF) {
                        dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + cost[u][v]);
                    }
                }
            }
        }
    }

    // Calculul rezultatului final: cel mai mic cost pentru a vizita toate nodurile și a reveni la start
    int result = INF;
    for (int i = 0; i < N; i++) {
        result = min(result, dp[(1 << N) - 1][i]);
    }

    if (result == INF) {
        outfile << "Nu exista solutie" << endl;
    } else {
        outfile << result << endl;
    }

    infile.close();
    outfile.close();

    return 0;
}