#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

FILE *fin, *fout;

#define MAXN 18
#define MAXM 18 * 17
#define inf (int)1e9

int N, M;
std::vector <int> v[MAXN + 1];
int cost[MAXN + 1][MAXN + 1];
int c[1 + (1 << MAXN)][MAXN + 1];

inline int calc(int conf, int lst)  {
    if(c[conf][lst] == -1)  {
        c[conf][lst] = inf;
        for(auto &x : v[lst])  {//iau fiecare nod din x
            if(conf & (1 << x))  {//ma asigur ca nu am mai trecut prin x
                if(x == 0 && conf != (1 << lst) + 1)
                    continue;//il scot pe 0 ultimul ( conditia zice asa:
                    // daca am gasit un x care sa fie chiar 0 si in configuratie inca sa mai existe
                    //noduri in afara de 0 si de lst, atunci mai trb sa fac pasi (trb sa trec si prin
                    //acele noduri din conf diferite de 0 si lst)
                c[conf][lst] = std::min(c[conf][lst], calc(conf ^ (1 << lst), x) + cost[lst][x]);
            }
        }
    }
    return c[conf][lst];
}

int main()  {
    fin = fopen("hamilton.in", "r");
    fout = fopen("hamilton.out", "w");
    fscanf(fin, "%d%d", &N, &M);
    for(int i = 0;i < MAXN;i++)
        for(int j = 0;j < MAXN;j++)
            cost[i][j] = inf;
    for(int i = 1;i <= M;i++)  {
        int x, y, c;
        fscanf(fin, "%d%d%d", &x, &y, &c);
        v[x].push_back(y);
        cost[x][y] = c;
    }
    memset(c, -1, sizeof c);
    c[1][0] = 0;
    int ans = inf;
    for(size_t i = 0;i < v[0].size();i++)  {
        int el = v[0][i];
        ans = std::min(ans, calc((1 << N) - 1, el) + cost[0][el]);
    }
    if(ans == inf)  {
        fprintf(fout, "Nu exista solutie");
        return 0;
    }
    fprintf(fout, "%d", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}