// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

//dp[mask][i] = cel mai scurt lant de la 0 la i
//care trece prin nodurile din mask

//dp[2^n - 1][i] + cost(i, 0)

//dp[mask][i] = dp[mask - 2^i][j] + cost(j, i)

//O((n + m) * 2^n)

const int INF = 1e9;
const int NMAX = 18;
int cost[NMAX + 1][NMAX + 1];
vector<int> L[NMAX + 1];
int dp[(1 << NMAX) + 1][NMAX + 1];

int main() {
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
	int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cost[i][j] = INF;
        }
    }
    for(int i = 1; i <= m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        cost[x][y] = c;
        L[y].push_back(x);
    }
    for(int i = 0; i < (1 << n); i++) {
        for(int j = 0; j < n; j++) {
            dp[i][j] = INF;
        }
    }
    dp[1][0] = 0;
    for(int mask = 1; mask < (1 << n); mask++) {
        for(int i = 1; i < n; i++) {
            if(mask & (1 << i)) {
                for(auto pre : L[i]) {
                    dp[mask][i] = min(dp[mask][i], dp[mask - (1 << i)][pre] + cost[pre][i]);
                }
            }
        }
    }
    int sol = INF;
    for(int i = 1; i < n; i++) {
        sol = min(sol, dp[(1 << n) - 1][i] + cost[i][0]);
    }
    if(sol == INF) {
        cout << "Nu exista solutie";
    } else {
        cout << sol;
    }
}