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

const int NMAX = 20;
int c[NMAX][NMAX], dp[(1 << NMAX)][NMAX];
const int INF = 1e9;
vector<int> a[NMAX];

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

int main() {
    int n, m;
    f >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            c[i][j] = INF;
        }
    }
    while(m--) {
        int x, y, z;
        f >> x >> y >> z;
        c[x][y] = z;
        a[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(int k = 0; k < (int)a[i].size(); k++) {
                    int nod = a[i][k];
                    dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][nod] + c[nod][i]);
                }
            }
        }
    }
    int sol = 1e9;
    for(int i = 1; i < n; i++) {
        sol = min(sol, dp[(1 << n) - 1][i] + c[i][0]);
    }
    if(sol == 1e9) {
        g << "Nu exista solutie\n";
    } else {
        g << sol;
    }
    return 0;
}