#include <fstream>
#include <vector>
#include <algorithm> // Pentru std::min

using namespace std;

const int INF = 1e9 + 7; // Un infinit sigur

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

vector<pair<int, int>> inv_adj[18]; // Graful tău invers, perfect pentru DP
vector<pair<int, int>> adj_normal[18]; // Un graf normal, doar pentru final
int dp[1 << 18][18];

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        inv_adj[b].push_back({a, c});
        adj_normal[a].push_back({b, c}); // Populăm și graful normal
    }

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

    // --- PARTEA TA DE DP, CARE ACUM ESTE CORECTĂ ---
    for (int msk = 1; msk < (1 << n); msk++) {
        for (int i = 0; i < n; i++) {
            if (msk & (1 << i)) {
                int prev_msk = (msk ^ (1 << i));
                if (prev_msk == 0) continue;

                for (auto& j : inv_adj[i]) { // j este {predecesor, cost}
                    if (prev_msk & (1 << j.first)) {
                        if (dp[prev_msk][j.first] != INF) {
                           dp[msk][i] = min(dp[msk][i], dp[prev_msk][j.first] + j.second);
                        }
                    }
                }
            }
        }
    }
    // --- SFÂRȘIT PARTE DP ---

    // --- RĂSPUNSUL FINAL - LOGICA CORECTATĂ ---
    int rezultat_final = INF;
    int masca_finala = (1 << n) - 1;

    for (int i = 0; i < n; i++) {
        if (dp[masca_finala][i] != INF) {
            // Căutăm muchia de întoarcere de la 'i' la '0' în graful normal
            for (auto& muchie : adj_normal[i]) {
                if (muchie.first == 0) { // Am găsit o muchie spre nodul 0
                    rezultat_final = min(rezultat_final, dp[masca_finala][i] + muchie.second);
                }
            }
        }
    }

    if (rezultat_final == INF) {
        fout << "Nu exista solutie";
    } else {
        fout << rezultat_final;
    }

    return 0;
}