#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int INF = 1e9;

int main() {
    int n, m;
    f >> n >> m;

    
    vector<vector<pair<int, int>>> adj(n);

    for (int i = 0; i < m; ++i) {
        int u, v, cost;
        f >> u >> v >> cost;
        adj[u].push_back({v, cost});
    }

    vector<vector<int>> dist(1 << n, vector<int>(n, INF));

    dist[1][0] = 0;

    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            
            if (dist[mask][i] != INF) {
                
                for (auto& edge : adj[i]) {
                    int neighbor = edge.first;
                    int cost = edge.second;

                
                    if (!((mask >> neighbor) & 1)) {
                        int newMask = mask | (1 << neighbor);
                        
                        
                        if (dist[newMask][neighbor] > dist[mask][i] + cost) {
                            dist[newMask][neighbor] = dist[mask][i] + cost;
                        }
                    }
                }
            }
        }
    }

    int fullMask = (1 << n) - 1;
    int minCost = INF;

    for (int i = 0; i < n; ++i) {
        if (dist[fullMask][i] != INF) {
            
            for (auto& edge : adj[i]) {
                if (edge.first == 0) {
                    minCost = min(minCost, dist[fullMask][i] + edge.second);
                }
            }
        }
    }

    if (minCost == INF) {
        g << "Nu exista solutie"; 
    } else {
        g << minCost;
    }

    return 0;
}