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

struct NODE {
    int node, cost, vis;
};

int n, m, cost[1 << 18][18];
queue<NODE> q;
vector<vector<pair<int, int>>> v(18);
int ans = INT_MAX;

void bfs() {
    memset(cost, 0x3f, sizeof(cost));
    q.push({0, 0, 1});
    cost[1][0] = 0;
    while (!q.empty()) {
        int node = q.front().node;
        int vis = q.front().vis;
        q.pop();
        for (int i = 0; i < v[node].size(); ++i) {
            int neigh = v[node][i].first;
            int ncost = v[node][i].second;
            if (!(vis & (1 << neigh)) && cost[vis][node] + ncost < cost[vis | (1 << neigh)][neigh]) {
                cost[vis | (1 << neigh)][neigh] = cost[vis][node] + ncost;
                q.push({neigh, cost[vis | (1 << neigh)][neigh], vis | (1 << neigh)});
            }
            if (neigh == 0 && vis == (1 << n) - 1 && cost[vis][node] + ncost < ans) {
                ans = cost[vis][node] + ncost;
            }
        }
    }
}

int main() {
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        v[x].push_back({y, c});
    }
    bfs();
    if (ans != INT_MAX) {
        cout << ans;
    } else {
        cout << "Nu exista solutie";
    }
}