Little I has invented an $O(n + m)$ algorithm for finding the minimum cycle in a directed graph, and now 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 the weights of the edges in the cycle is minimized. Find 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 has relaxed the conditions: it is guaranteed that the input graph is weakly connected, and $m-n$ is not very large. A graph is weakly connected if and only if the graph is connected when directed edges are replaced by undirected edges.

Input

The input is read from standard input.

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.

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$. It is guaranteed that the graph is weakly connected.

Output

The output is written to standard output.

If there is no cycle in the graph, output -1; otherwise, output an integer representing the sum of the weights of the minimum cycle.

Examples

Input 1

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

Output 1

7

Note 1

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

Input 2

1 0

Output 2

-1

Input 3

1 1
1 1 1

Output 3

1

Note 3

The minimum cycle is $1 \to 1$.