버블 정렬

최근 어린 Z는 버블 정렬에 강한 관심을 갖게 되었다.

버블 정렬의 의사코드는 다음과 같다.

입력: 길이가 n인 수열 a[1...n]
출력: 작은 수부터 큰 수 순으로 정렬된 결과
  for i = 1 to n do:
    for j = 1 to n - 1 do
      if (a[j] > a[j + 1])
          a[j]와 a[j + 1]의 값을 교환한다

버블 정렬의 교환 횟수는 정렬 중에 수행된 교환의 수이며, 위 의사코드에서 여섯 번째 줄이 실행되는 횟수와 같다. 그는 교환 횟수가 가능한 한 적은 수열을 찾고 싶어 한다.

어린 Z가 연구하는 수열은 음이 아닌 정수로 이루어진다. 수열의 길이는 $n$이며, 다음 $m$개의 조건을 만족해야 한다.

$i$번째 조건: 인덱스가 $L_i$부터 $R_i$까지인 원소 $a[L_i], a[L_i+1], \ldots, a[R_i]$의 최솟값이 정확히 $V_i$이다.

버블 정렬은 시간 초과가 자주 난다. 그래서 그는 모든 조건을 만족하는 수열 중에서 버블 정렬의 교환 횟수가 최소가 되는 값을 알고 싶어 한다.

여러 개의 데이터가 주어진다. 첫 줄에 양의 정수 $T$가 주어진다. 각 데이터의 첫 줄에는 양의 정수 $n$, $m$이 주어진다. 여기서 $1 \leq n, m \leq 10^6$이다. 다음 $m$개의 줄에는 음이 아닌 정수 $L_i$, $R_i$, $V_i$가 주어지며, $1 \leq L_i \leq R_i \leq n$, $0 \leq V_i \leq 10^9$을 만족한다.

$T$개의 줄에 정수를 한 줄에 하나씩 출력한다. 모든 조건을 만족하는 수열이 있으면, 그러한 수열들 중 버블 정렬의 교환 횟수 최솟값을 출력한다. 모든 조건을 만족하는 수열이 없으면 $-1$을 출력한다.

모든 테스트 포인트는 다음을 만족한다: $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$. 여기서 $\sum n$과 $\sum m$은 모든 테스트 포인트의 $n$과 $m$의 합이다.

일부 테스트 포인트는 입력량이 많다. 빠른 입출력을 사용하는 것을 권장한다.