#include <bits/stdc++.h>

using namespace std;

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

#define NMAX 18
#define INT_MAX 1000000000

vector<int> g[NMAX];

int dp[NMAX][1 << NMAX];
int cs[NMAX][NMAX];
int n, m;

void add(int x, int y, int c) {
    g[x].push_back(y);
    cs[x][y] = c;
}

void memset() {
    for(int i = 0; i <= NMAX; i++)
        for(int j = 0; j <= NMAX; j++)
            cs[i][j] = INT_MAX;
    for(int i = 0; i < (1 << NMAX); i++)
        for(int j = 0; j < NMAX; j++)
            dp[j][i] = INT_MAX;
    dp[0][1] = 0;
}

void getmin() {
    int mini = INT_MAX;
    for(int i = 1; i < n; i++)
        mini = min(mini, dp[i][(1 << n) - 1] + cs[i][0]);
    if(mini == INT_MAX)
        out << "Nu exista solutie";
    else
        out << mini;

}

int main() {
    int i, x, y, c, mask;
    in >> n >> m;
    memset();

    for(i = 0; i < m; i++) {
        in >> x >> y >> c;
        add(x, y, c);
    }

    for(mask = 0; mask < (1 << n); mask++)
        for(i = 0; i < n; i++)
            if(mask & (1 << i))
                for(int j : g[i])
                    if(mask & (1 << j))
                        dp[j][mask] = min(dp[j][mask], dp[i][mask - (1 << j)] + cs[i][j]);
    getmin();

    return 0;
}