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

using namespace std;

ifstream f ("hamilton.in");
ofstream g ("hamilton.out");

const int NMAX = 18 + 1 + 1;
const int INF = 0X3fffffff;

int n, m;
vector < pair <int, int> > graf[NMAX];
int d1[NMAX];
int sol[NMAX][1 << NMAX];

void citeste() {
    int a, b, c;
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        f >> a >> b >> c;
        a++; b++;
        graf[a].push_back(make_pair(b, c));
        if (b == 1) d1[a] = c;
    }
}

int hamilton (int nod, int configuratie) {
    if(sol[nod][configuratie] != 0) return sol[nod][configuratie];
    if (configuratie == (1 << (n + 1)) - 2) { //am ajuns la final (1111110)
        if (d1[nod] != 0) sol[nod][configuratie] = d1[nod];
        else sol[nod][configuratie] = INF; // nu e o solutie
    }
    else {
        int minim = INF, crt, l = graf[nod].size(), fiu, c;
        for (int i = 0; i < graf[nod].size(); i++) {
            fiu = graf[nod][i].first;
            c = graf[nod][i].second;
            if((configuratie & (1 << fiu)) == 0) {
                crt = c + hamilton(fiu, configuratie ^ (1 << fiu));
                minim = min(minim, crt);
            }
        }
        sol[nod][configuratie] = minim;
    }

    return sol[nod][configuratie];
}

int main() {
    citeste();
    int c = hamilton(1, 1 << 1);
    if (c == INF) g << "Nu exista solutie";
    else g << c;
    g << '\n';
    return 0;
}