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

using namespace std;

const int MAXVAL = 2000000000;

FILE *f = fopen("hamilton.in", "r");
FILE *h = fopen("hamilton.out", "w");

int n, m;

int cost[20][20], rez[20][280000];

vector<int> graf[20];

int solve(int lant, int last) {
    if (rez[last][lant] == -1) {
        rez[last][lant] = MAXVAL;
        for (int i = 0; i < graf[last].size(); ++i) {
            if (lant & (1 << graf[last][i])) {
                if (graf[last][i] == 0 && lant != (1 << last) + 1)
                    continue;
                rez[last][lant] = min(rez[last][lant], solve(lant ^ (1<<last), graf[last][i]) + cost[graf[last][i]][last]);
                //printf("%d\n", solve(lant ^ (1<<last), graf[last][i]));
            }
        }
    }
    return rez[last][lant];
}

int main() {
    fscanf(f, "%d %d", &n, &m);
    memset(rez, -1, sizeof(rez));
    for (int i = 1; i <= m; ++i) {
        int x, y;
        fscanf (f, "%d %d ", &x, &y);
        fscanf (f, "%d\n", &cost[x][y]);
        //cost[x][y] = cost[y][x];
        graf[y].push_back(x);
    }
    rez[0][1] = 0;
    int ans = MAXVAL;
    for (int i = 0; i < graf[0].size(); ++i) {
        ans = min(ans, solve((1 << n) - 1, graf[0][i]) + cost[graf[0][i]][0]);
    }
    if (ans == MAXVAL) {
        fprintf(h,"Nu exista solutie");
    } else {
        fprintf(h, "%d", ans);
    }
    return 0;
}