Background

Recently, little Z has developed a strong interest in bubble sorting.

Here is the pseudocode for bubble sort:

Input: a sequence a[1...n] of length n
Output: a result sorted from small to large
  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, which is the number of times the sixth line of the above bubble sort pseudocode is executed. He wants to find a sequence with as few exchanges as possible.

Task Description

The sequences studied by little Z consists of non-negative integers. It is of length $n$ and must satisfy $m$ additional conditions.

The $i$-th condition is: the minimum of the numbers with indices in $[L[i],R[i]]$, namely $a[L[i]],a[L[i]+1],\dots ,a[R[i]]$, is exactly $V[i]$.

He knows that bubble sort often times out. So, he wants to know what is the minimum number of swaps for bubble sort among all sequences that satisfy the additional condition.

Input Specification

There are multiple sets of data in this question.

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

For each set of data, the first row contains two positive integers n, m. Data guarantees $1\le n,m\le {10}^6$.

The next m lines, each with three non-negative integers $L[i],R[i],V[i]$, represent a set of additional conditions. Data guarantees $1\le L[i]\le R[i]\le n,0\le V[i]\le {10}^9$.

Output Specifiction

The output is $T$ lines in total, one integer per line.

For each set of data, if there are sequences that satisfy the m additional conditions, output the minimum number of exchanges in bubble sort among all the sequences that satisfy the additional conditions. If there is no sequence satisfying all conditions, output $-1$.

Sample Input 1

1
3 2
1 1 2022
2 3 39

Sample Output 1

1

Explanation for Sample Output 1

The constraints for this set of data are $a[1]=2022,min\{a[2],a[3]\}=39$.

If $a[2]=39$, and $39\le a[3]<2022$, then the bubble sort has only the first round of swap operations. This round swaps $a[1],a[2]$ and $a[2],a[3]$, and the total number of swaps is $2$.

If $a[2]=39$, and $a[3]\ge 2022$, the bubble sort has only the first round of exchange operations, this round only exchanges $a[1],a[2]$, and the total number of exchanges is $1$.

If $a[3]=39$, and $39<a[2]<2022$, the bubble sort algorithm swaps $a[1],a[2]$ and $a[2],a[3]$ in the first round and $a[1],a[2]$ in the second round. The total number of swaps is $3$.

If $a[3]=39$, and $a[2]\ge 2022$, the bubble sort algorithm exchanges $a[2],a[3]$ in the first round, and exchanges $a[1],a[2]$ in the second round. The total number of swaps is $2$.

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

Additional Samples

Sample inputs and outputs can be found here.

• Sample 2 (bubble2.in and bubble2.ans).
• Sample 3 (bubble3.in and bubble3.ans) corresponds to test cases 8-10.
• Sample 4 (bubble4.in and bubble4.ans) corresponds to test cases 13-14.
• Sample 5 (bubble5.in and bubble5.ans) corresponds to test cases 15-16.
• Sample 6 (bubble6.in and bubble6.ans) corresponds to test cases 23-25.

Constraints

There are 25 test cases in this question. All test points satisfy: $1\le T\le 1000$, $1\le \sum n,\sum m\le {10}^6$, $1\le L[i]\le R[i]\le n$, $0\le V[i]\le {10}^9$.

Case	Constraints	Special Property
1 - 4		$n,m\le 7$, all but 2 cases have $n,m\le 5$
5 - 7	$n,m\le 17$, all but 3 cases have $n,m\le 9$	A
8 - 10	$n,m\le 100$, $\sum n^3,\sum m^4\le 4\cdot {10}^7$
11, 12	$n,m\le 2000$, $\sum n^2,\sum m^2\le 4\cdot {10}^7$
13, 14		B
15, 16		C
17, 18
19	$\sum n,\sum m\le {10}^6$	A
20		B
21, 22		C
23, 24, 25

where $\sum n,\sum m$ represent the sum of $n$ and $m$ of all test points, respectively. $\sum n^2,\sum m^2,\sum n^3,\sum m^3$ meanings are similar.

• Special property A: For $1\le i\le m,0\le V[i]\le 1$.
• Special property B: $L[i]=R[i]for1\le i\le m$.
• Special property C: The input gives $m$ intervals $[L[i],R[i]]$ Pairs do not intersect.

Hint

Some of the test points in this question have a large amount of input. We recommend that you use the fast I/O.