Problem Description

Little I invented an $O(n + m)$ algorithm for the minimum cycle in a directed graph, so he wants to test you.

Given a directed graph with $n$ nodes and $m$ edges, where each edge has a positive integer weight. You need to find a cycle in the graph such that the sum of edge weights on the cycle is minimized. Output this minimum value, or report that no cycle exists.

Of course, since you do not know the $O(n + m)$ algorithm for the minimum cycle in a directed graph, Little I relaxed the conditions: the input graph is guaranteed to be weakly connected, and $m-n$ will not be very large. A graph is weakly connected if and only if it becomes connected after replacing directed edges with undirected edges.

Input Format

The first line contains two integers $n, m \ (1 \le n \le 3 \times 10^5, -1 \le m-n \le 1500)$, representing the number of nodes and edges in the graph.

The next $m$ lines each contain three integers $u_i, v_i, w_i \ (1 \le u_i, v_i \le n, 1 \le w_i \le 10^9)$, describing a directed edge from $u_i$ to $v_i$ with weight $w_i$. The graph is guaranteed to be weakly connected.

Output Format

If there is no cycle in the graph, output -1. Otherwise, output one integer representing the minimum cycle total weight.

4 6
1 2 1
4 3 3
4 1 9
2 4 1
3 1 2
3 2 6

7

1 0

-1

1 1
1 1 1

1

Hint

[Sample Explanation 1]

The minimum cycle is $1 \to 2 \to 4 \to 3 \to 1$.

[Sample Explanation 3]

The minimum cycle is $1 \to 1$.

Translated by ChatGPT 5