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

using namespace std;

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

const int INF = (1 << 30);
const int NMAX = 18;

int n, m;
int cost[NMAX][NMAX];
int dp[NMAX + 1][(1 << NMAX)];

void citeste() {
    int a, b, c;

    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        f >> a >> b >> c;
        a++; b++;
        cost[a][b] = c;
    }
}

int hamilton(int config, int x) {
    if (dp[x][config]) return dp[x][config];
    else if (config == (1 << n) - 1) {
        if (cost[x][1] == 0) return INF;
        dp[x][config] = cost[x][1];
        return cost[x][1];
    }

    int d = INF;

    for (int i = 2; i <= n; i++)
        if (cost[x][i] != 0 && !(config & (1 << (i - 1)))) {
            //cout << x << ' ' << i << endl;
            d = min(d, hamilton(config | (1 << (i - 1)), i) + cost[x][i]);
        }
    if (d == -1) d = INF;

    dp[x][config] = d;
    return d;
}

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