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

#define MAX_N 18

struct Edge {
    int node;
    int cost;
};

int noNodes, noEdges;
vector<Edge> graph[MAX_N];

int minCost;
bool marked[MAX_N];
vector<int> cycle;

void addEdge(int x, int y, int cost) {
    graph[x].push_back({y, cost});
}

void dfs(int node, int cost) {
    marked[node] = true;
    cycle.push_back(node);

    for (const Edge& edge : graph[node])
        if (!marked[edge.node])
            dfs(edge.node, cost + edge.cost);
        else if (cycle.size() == noNodes && edge.node == cycle.front())
            minCost = min(minCost, cost + edge.cost);

    marked[node] = false;
    cycle.pop_back();
}

int main() {
    FILE *fin, *fout;
    fin = fopen("hamilton.in", "r");
    fout = fopen("hamilton.out", "w");

    int i, x, y, cost;

    fscanf(fin, "%u%u", &noNodes, &noEdges);
    for (i = 0; i < noEdges; ++i) {
        fscanf(fin, "%d%d%d", &x, &y, &cost);
        addEdge(x, y, cost);
    }

    minCost = INT_MAX;
    dfs(0, 0);

    if (minCost == INT_MAX)
        fprintf(fout, "Nu exista solutie\n");
    else
        fprintf(fout, "%d\n", minCost);

    fclose(fin);
    fclose(fout);
    return 0;
}