Fast Algorithm

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

You are given a directed graph with $n$ vertices 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 edge weights on the cycle is minimized. Output the minimum value of this sum or report if there is no cycle.

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

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

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

Print a line with a single integer: the length of the minimum cycle in the graph, or $-1$ if there is no cycle.

In the first example, the minimum cycle is $1 \to 2 \to 4 \to 3 \to 1$.