Minimum Cycle in a Directed Graph

Little I invented an algorithm that finds the minimum cycle in a directed graph in \(O(n + m)\) time, and now he wants to test you.

You are given a directed graph with \(n\) nodes and \(m\) edges. Each edge has a positive integer weight. Your task is to find a cycle in the graph such that the sum of the weights on the cycle is minimized. Output this minimum total weight, or report that there is no cycle.

Note that since you do not know the \(O(n + m)\) algorithm, Little I has relaxed the conditions: it is guaranteed that the input graph is weakly connected (i.e. the graph becomes connected if all directed edges are replaced by undirected edges), and \(m - n\) is not very large.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n \leq \text{some limit},\; 0 \leq m \leq \text{some limit})\) representing the number of nodes and edges respectively. Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\) \((1 \leq u, v \leq n,\; 1 \leq w \leq \text{some limit})\) indicating there is a directed edge from node \(u\) to node \(v\) with weight \(w\).

outputFormat

If there is at least one cycle, output a single integer: the minimum cycle weight. Otherwise, output impossible.

sample

3 3
1 2 1
2 3 2
3 1 3

6