Problem Description

Little I has invented an $O(n + m)$ algorithm for finding the minimum cycle in a directed graph, and he wants to test your skills.

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 the weights of the edges in the cycle is minimized. Output this minimum value, or report that no cycle exists.

Since you do not know the $O(n + m)$ algorithm for finding the minimum cycle in a directed graph, Little I has relaxed the conditions: The input graph is guaranteed to be weakly connected, and $m - n$ is not very large. A graph is weakly connected if and only if the graph remains connected when all directed edges are replaced 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, respectively.

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)$, indicating a directed edge from $u_i$ to $v_i$ with a weight of $w_i$. The graph is guaranteed to be weakly connected.

Output Format

If no cycle exists in the graph, output -1. Otherwise, output an integer representing the minimum sum of the weights of the edges in the cycle.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7

Sample Input #2

1 0

Sample Output #2

-1

Sample Input #3

1 1
1 1 1

Sample Output #3

1

Notes

[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$.

见题面 Input 部分

见题面 Output 部分