Problem Description

There is a graph with \( N + Q \) vertices, numbered \( 1, 2, \ldots, N + Q \). Initially, the graph has no edges.

For each \( i = 1, 2, \ldots, Q \) in this order, perform the following operation:

• For each integer \( j \) satisfying \( L_i \leq j \leq R_i \), add an undirected edge with cost \( C_i \) between vertex \( N + i \) and vertex \( j \).

After all operations, determine if the graph is connected. If it is connected, find the cost of the minimum spanning tree of this graph.

A minimum spanning tree is a spanning tree with the minimum cost, and the cost of a spanning tree is the sum of the costs of the edges used in the spanning tree.

Input Format

The input is given from the standard input in the following format:

\( N \) \( Q \) \( L_1 \) \( R_1 \) \( C_1 \) \( L_2 \) \( R_2 \) \( C_2 \) \( \vdots \) \( L_Q \) \( R_Q \) \( C_Q \)

Output Format

If the graph is connected, output the cost of the minimum spanning tree. Otherwise, output \( -1 \).

Sample Input and Output

Sample Input #1

4 3
1 2 2
1 3 4
2 4 5

Sample Output #1

22

Sample Input #2

6 2
1 2 10
4 6 10

Sample Output #2

-1

Sample Input #3

200000 4
1 200000 1000000000
1 200000 998244353
1 200000 999999999
1 200000 999999999

Sample Output #3

199651870599998

Notes/Hints

Constraints

• \( 1 \leq N, Q \leq 2 \times 10^5 \)
• \( 1 \leq L_i \leq R_i \leq N \)
• \( 1 \leq C_i \leq 10^9 \)
• All values input are integers.

Sample Explanation 1

One of the minimum spanning trees consists of the following edges:
- Edge with cost \( 2 \) between vertices \( 1 \) and \( 5 \)
- Edge with cost \( 2 \) between vertices \( 2 \) and \( 5 \)
- Edge with cost \( 4 \) between vertices \( 1 \) and \( 6 \)
- Edge with cost \( 4 \) between vertices \( 3 \) and \( 6 \)
- Edge with cost \( 5 \) between vertices \( 3 \) and \( 7 \)
- Edge with cost \( 5 \) between vertices \( 4 \) and \( 7 \)

The sum of the costs is \( 2 + 2 + 4 + 4 + 5 + 5 = 22 \), so output \( 22 \).

Sample Explanation 2

The graph is not connected.

见题面 Input 部分

见题面 Output 部分