Background

Recently, Little Z has become very interested in bubble sort.

Below is the pseudocode of bubble sort:

Input: a sequence a[1...n] of length n
Output: the result of sorting a in nondecreasing order
for i = 1 to n do:
    for j = 1 to n - 1 do
        if (a[j] > a[j + 1])
            swap the values of a[j] and a[j + 1]

The number of swaps in bubble sort is defined as the number of swaps performed during sorting, that is, the number of times line 6 of the bubble sort pseudocode above is executed. He wants to find a sequence with as few swaps as possible.

Background

Problem Description

All sequences studied by Little Z consist of nonnegative integers. The length of the sequence is $n$, and it must satisfy $m$ additional constraints. The $i$-th constraint is:

Among the numbers whose indices lie in $[L_i, R_i]$, i.e., $a_{L_i}, a_{L_{i+1}},\dots,a_{R_i}$, the minimum value is exactly $\boldsymbol{V_i}$.

He knows that bubble sort often times out. Therefore, he wants to know: among all sequences that satisfy the additional constraints, what is the minimum possible number of swaps performed by bubble sort?

Input Format

This problem contains multiple test cases.

The first line of input contains a positive integer $T$.

For each test case, the first line contains two positive integers $n, m$. The data guarantee that $1 \leq n, m \leq 10^6$.

In the next $m$ lines, each line contains three nonnegative integers $L_i, R_i, V_i$, representing one additional constraint. The data guarantee that $1 \leq L_i \leq R_i \leq n$, and $0 \leq V_i \leq 10^9$.

Output Format

Output $T$ lines in total, each line containing one integer.

For each test case, if there exists a sequence satisfying all $m$ additional constraints, output the minimum number of bubble sort swaps among all such sequences. If no sequence satisfies all constraints, output $-1$.

1
3 2
1 1 2022
2 3 39

1

Hint

[Sample Explanation #1]

The constraints for this test case are $a_1 = 2022$ and $\min\{a_2, a_3\} = 39$.

If $a_2 = 39$ and $39 \leq a_3 < 2022$, then bubble sort performs swaps only in the first pass. In this pass, it swaps $a_1, a_2$ and $a_2, a_3$, so the total number of swaps is $2$.

If $a_2 = 39$ and $a_3 \geq 2022$, then bubble sort performs swaps only in the first pass. In this pass, it swaps only $a_1, a_2$, so the total number of swaps is $1$.

If $a_3 = 39$ and $39 < a_2 < 2022$, then in the first pass bubble sort swaps $a_1, a_2$ and $a_2, a_3$, and in the second pass it swaps $a_1, a_2$. The total number of swaps is $3$.

If $a_3 = 39$ and $a_2 \geq 2022$, then in the first pass bubble sort swaps $a_2, a_3$, and in the second pass it swaps $a_1, a_2$. The total number of swaps is $2$.

Therefore, the minimum number of swaps is $1$.

[Sample #2]

See bubble/bubble2.in and bubble/bubble2.ans in the attachment.

[Sample #3]

See bubble/bubble3.in and bubble/bubble3.ans in the attachment.

This sample satisfies the conditions of test points $8 \sim 10$.

[Sample #4]

See bubble/bubble4.in and bubble/bubble4.ans in the attachment.

This sample satisfies the conditions of test points $13 \sim 14$.

[Sample #5]

See bubble/bubble5.in and bubble/bubble5.ans in the attachment.

This sample satisfies the conditions of test points $15 \sim 16$.

[Sample #6]

See bubble/bubble6.in and bubble/bubble6.ans in the attachment.

This sample satisfies the conditions of test points $23 \sim 25$.

[Constraints]

This problem has $25$ test points. All test points satisfy: $1 \leq T \leq 1000$, $1 \leq \sum n, \sum m \leq 10^6$, $1 \leq L_i \leq R_i \leq n$, $0 \leq V_i \leq 10^9$.

Here, $\sum n$ and $\sum m$ denote the total sum of $n$ and the total sum of $m$ over all test points. The meanings of $\sum n^2, \sum m^2, \sum n^3, \sum m^3$ are similar.

Special property A: For $1 \leq i \leq m$, $0 \leq V_i \leq 1$.
Special property B: For $1 \leq i \leq m$, $L_i = R_i$.
Special property C: The $m$ intervals $[L_i, R_i]$ given in the input are pairwise disjoint.

[Hint]

For some test points, the input size is large. We recommend using a faster input method.

Translated by ChatGPT 5