지하철 입장 카드 교환

도시가 첫 지하철 노선을 개통했다. 역은 $N$개이고 1번부터 $N$번까지 번호가 붙어 있다. 요금은 승차권이 아니라 입장 카드로 계산한다.

지하철에 들어가는 승객은 입장 카드를 한 장 받는다. 카드에는 승객이 들어간 역이 적혀 있다. 나갈 때는 카드를 한 장 반납해야 하고, 카드에 적힌 역과 카드를 반납하는 역 사이의 거리에 따라 요금을 낸다.

• 두 역이 같으면 요금을 내지 않는다.
• 두 역이 인접하면 $N$파운드를 낸다.
• 거리가 두 역이면 $2N - 1$을 낸다. 첫 번째 정거장에 $N$, 두 번째 정거장에 $N - 1$이 붙는다.
• 세 번째 정거장에는 $N - 2$가 붙으므로 세 역을 이동하면 $3N - 3$을 낸다. 네 번째 정거장에는 $N - 3$이 붙고, $i$번째 정거장에는 $N + 1 - i$가 붙는다.
• 따라서 노선의 한쪽 끝에서 반대쪽 끝까지 가면(거리 $N - 1$) 마지막 역에 2파운드가 붙고 전체 요금은 $(N^2 + N - 2) / 2$가 된다.

이 제도를 들인 뒤 도시는 수입이 기대만큼 늘지 않는다는 사실을 알아차렸다. 원인은 승객끼리 입장 카드를 바꾸는 것이었다. 예를 들어 한 사람이 역 $A$에서 들어가 두 역을 이동해 역 $B$에서 나가고, 다른 사람이 역 $B$에서 들어가 세 역을 이동해 역 $C$에서 나간다고 하자. 원래 두 사람이 내는 요금은 모두 합쳐 $2N - 1 + 3N - 3 = 5N - 4$다. 그런데 두 사람이 역 $B$에서 카드를 바꾸면, 첫 번째 사람은 $B$가 적힌 카드를 역 $B$에서 반납하므로 거리가 0이 되어 공짜로 이동한다. 두 번째 사람은 역 $C$에서 $A$가 적힌 카드를 반납하는데, 두 역의 거리가 5이므로 $5N - 10$을 낸다. 도시는 6파운드를 손해 본다.

도시는 이런 교환이 널리 퍼지면 얼마까지 손해를 볼 수 있는지 알고 싶다. 노선은 1번 역에서 $N$번 역까지 모든 역을 순서대로 지나는 한 방향만, 열차는 한 대만 생각한다. $o$번 역에서 타서 $e$번 역에서 내리는 승객은 $o$에서 카드를 받고, $o$와 $e$ 사이 어디서든 다른 승객과 카드를 몇 번이든 바꿀 수 있다. $o$에서 내리는 사람이나 $e$에서 타는 사람과도 바꿀 수 있다. 그리고 $e$에서 카드를 한 장 반납하고 나간다. 나가려면 반드시 카드를 한 장 반납해야 한다. 승객은 중간에 열차에서 내리지 않는다. 즉 들고 있던 카드를 반납하고 새 카드를 받는 일은 없다.

어느 역에서 어느 역까지 몇 명이 이동하는지 적은 교통량 표가 주어진다. 승객이 손해를 최대로 만들도록 카드를 바꾼다고 할 때, 도시가 입는 손해를 구하여라. 손해는 아무도 카드를 바꾸지 않았을 때의 총요금에서, 카드를 바꿔 만들 수 있는 총요금의 최솟값을 뺀 값이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 역의 수 $N$과 출발역과 도착역 쌍의 수 $M$이 주어진다. 역은 1번부터 $N$번까지 번호가 붙어 있다. 이어지는 $M$개 줄에는 세 정수 $o_i$, $e_i$, $p_i$가 주어진다. $o_i$번 역에서 타서 $e_i$번 역에서 내리는 승객이 $p_i$명이라는 뜻이다.

제한:

• $1 \le T \le 20$
• $2 \le N \le 10^9$
• $1 \le M \le 1000$
• $1 \le o_i < e_i \le N$
• $1 \le p_i \le 10^9$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 카드 교환으로 도시가 입는 손해를 1000002013으로 나눈 나머지다.

첫 번째 예제 케이스는 문제에서 설명한 상황이다. 두 승객이 3번 역에서 만나 카드를 바꾼다. 두 번째 예제 케이스에서는 두 승객이 만나는 구간이 없어서 카드를 바꿀 수 없고, 도시가 입는 손해도 없다. 세 번째 예제 케이스에서는 먼저 탄 두 승객 가운데 한 명만 나중에 탄 승객과 카드를 바꿀 수 있다.