승차권 교환

도시는 총 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역에서 하차하며 반납하므로 거리가 영으로 기록된다). 한편 두 번째 사람은 C역에서 하차하며 5개 역 떨어진 A역이라고 명시된 입장 카드를 반납하고 5N - 10을 낸다. 그 결과 도시는 순수하게 여섯 파운드의 손실을 본다!

이제 도시는 이러한 행위가 널리 퍼질 경우 최대 얼마를 잃을 수 있는지 알고 싶어 한다. 지하철의 한 방향(역 1에서 역 N까지 모든 역을 순서대로 통과하는 방향)만 고려하며, 이 노선의 열차도 하나만 고려한다. o에서 e로 이동하는 승객은 o에서 입장 카드를 받고, o와 e 사이 어디에서든 다른 어떤 승객과도 입장 카드를 몇 번이든 교환할 수 있다고 가정한다. 여기에는 o에서 내리는 사람이나 e에서 타는 사람과의 교환도 포함된다. 그런 다음 승객은 어떤 입장 카드 하나를 가지고 e에서 열차에서 내린다(지하철에서 나가려면 반드시 입장 카드 하나를 반납해야 한다). 또한 승객은 그사이에 열차에서 내리지 않는다고 가정한다(즉, 현재 가진 카드를 반납하고 새 카드를 받지 않는다).

어느 역에서 어느 역까지 이 열차를 이용하는 승객이 몇 명인지 나타내는 교통 지도가 주어진다. 승객들이 도시의 손실을 최대화하도록 카드를 교환한다고 가정하고 도시의 금전적 손실을 계산해야 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 20. 1 ≤ $o_{i}$ < $e_{i}$ ≤ N

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ N ≤ 100. 1 ≤ M ≤ 100. 1 ≤ $p_{i}$ ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ N ≤ $10^{9}$. 1 ≤ M ≤ 1000. 1 ≤ $p_{i}$ ≤ $10^{9}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 정차역의 수 N(정차역에는 1부터 N까지 번호가 매겨진다)과 주어지는 출발지-도착지 쌍의 수 M이 포함된다. 다음 M개의 줄에는 각각 세 수가 주어진다. 출발역 $o_{i}$, 도착역 $e_{i}$, 그리고 이 여정을 이동하는 승객의 수 $p_{i}$이다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 승차권 교환 때문에 도시가 입을 수 있는 총손실을 1000002013로 나눈 나머지이다.

첫 번째 테스트 케이스는 문제 설명에서 다룬 경우로, 두 승객이 역 3에서 만나 승차권을 교환한다. 두 번째 테스트 케이스에서는 두 승객이 전혀 만나지 않으므로 승차권을 교환할 수 없다(따라서 도시는 손실을 입지 않는다). 세 번째 경우에는 먼저 출발한 승객들 중 한 명만 나중에 출발한 승객과 승차권을 교환할 수 있다.