#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 18;
const int MASK = (1 << NMAX);
const int INF = 1e9;

int N, M;
vector <pair<int,int>> g[NMAX + 2];

int dp[MASK + 2][NMAX + 2];

int main() {
    cin >> N >> M;

    for(int i = 1; i <= M; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        g[y].push_back({x, c});
    }

    for(int i = 0; i < (1 << N); i++) {
        for(int j = 0; j < N; j++) {
            dp[i][j] = INF;
        }
    }

    dp[1][0] = 0;
    ///dp[mask][j] -> costul minim sa vizitez nodurile din mask, ultimul nod vizitat fiind j

    for(int mask = 2; mask < (1 << N); mask++) {
        for(int j = 0; j < N; j++) {
            if(mask & (1 << j)) {
                for(pair <int, int> it : g[j]) {
                    if(mask & (1 << it.first)) {
                        dp[mask][j] = min(dp[mask][j], dp[mask ^ (1 << j)][it.first] + it.second);
                    }
                }
            }
        }
    }

    int minAns = INF;
    for(pair <int, int> it : g[0]) {
        minAns = min(minAns, dp[(1 << N) - 1][it.first] + it.second);
    }

    if(minAns == INF) {
        cout << "Nu exista solutie\n";
    } else {
        cout << minAns << '\n';
    }

    return 0;
}