#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int INF = 0x3f3f3f3f;

int main() {
    int numar_noduri, numar_muchii;
    fin >> numar_noduri >> numar_muchii;

    int cost_minim[1 << numar_noduri][numar_noduri];
    vector<int> lista_vecini[numar_noduri];
    int cost_muchie[numar_noduri][numar_noduri];

    for (int i = 0; i < numar_noduri; i++)
        fill(cost_muchie[i], cost_muchie[i] + numar_noduri, INF);

    int nod1, nod2, cost;
    for (int i = 0; i < numar_muchii; i++) {
        fin >> nod1 >> nod2 >> cost;
        lista_vecini[nod1].push_back(nod2);
        cost_muchie[nod1][nod2] = cost;
    }

    for (int permutare = 0; permutare < (1 << numar_noduri); permutare++)
        fill(cost_minim[permutare], cost_minim[permutare] + numar_noduri, INF);

    cost_minim[1][0] = 0;

   for (int permutare = 0; permutare < (1 << numar_noduri); permutare++) {
        for (int nod = 0; nod < numar_noduri; nod++) {
            if (!(permutare & (1 << nod))) continue;

            for (int vecin : lista_vecini[nod]) {
                if (permutare & (1 << vecin)) continue;

                int noua_submultime = permutare | (1 << vecin);
                cost_minim[noua_submultime][vecin] = min(cost_minim[noua_submultime][vecin], cost_minim[permutare][nod] + cost_muchie[nod][vecin]);
            }
        }
    }

    int cost_min = INF;
    for (int nod = 0; nod < numar_noduri; nod++)
        cost_min = min(cost_min, cost_minim[(1 << numar_noduri) - 1][nod] + cost_muchie[nod][0]);

    if (cost_min == INF)
        fout << "Nu exista solutie\n";
    else
        fout << cost_min << '\n';

    return 0;
}