승차 카드 바꿔치기 (작은 입력)

어떤 도시가 첫 지하철 노선을 열었다. 역은 모두 $N$개이고, 요금은 승차 카드로 계산한다.

승객은 지하철을 탈 때 승차 카드를 한 장 받는다. 카드에는 승객이 탄 역이 적혀 있다. 지하철에서 나갈 때는 카드를 반납해야 하고, 카드에 적힌 역과 나가는 역 사이의 거리(지나온 역의 수)에 따라 요금을 낸다.

• 두 역이 같으면 요금은 0파운드다.
• 두 역이 이웃하면 $N$파운드를 낸다.
• 거리가 두 역이면 $2N - 1$파운드를 낸다. 첫 번째 역에 $N$, 두 번째 역에 $N - 1$이 붙는다.
• 세 번째 역은 $N - 2$가 붙으므로 세 역을 가면 $3N - 3$을 낸다. 네 번째 역은 $N - 3$이고, $i$번째 역은 $N + 1 - i$다.
• 노선의 한쪽 끝에서 반대쪽 끝까지 가면 $N - 1$개 역을 지나고, 마지막 역에 2파운드가 붙어 모두 $\frac{N^2 + N - 2}{2}$파운드를 낸다.

제도를 시작한 뒤 도시는 수입이 기대보다 적다는 것을 알아차렸다. 승객끼리 승차 카드를 바꿔치기한 것이 원인이었다. 예를 들어 한 승객이 역 $A$에서 타서 두 역을 지나 $B$에서 내리고, 다른 승객이 $B$에서 타서 세 역을 지나 $C$에서 내린다고 하자. 원래대로면 두 사람이 내는 요금은 $2N - 1 + 3N - 3 = 5N - 4$다. 그런데 두 사람이 역 $B$에서 카드를 바꾸면, 첫 번째 승객은 $B$가 적힌 카드를 역 $B$에서 반납하므로 거리가 0이 되어 공짜로 탄다. 두 번째 승객은 $A$가 적힌 카드를 역 $C$에서 반납하는데, 그 거리가 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 100$
• $1 \le M \le 100$
• $1 \le o_i < e_i \le N$
• $1 \le p_i \le 100$

같은 $(o_i, e_i)$ 쌍이 여러 줄에 나올 수 있다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 카드 바꿔치기로 도시가 잃을 수 있는 최대 금액을 1000002013으로 나눈 나머지다.

예제의 첫 번째 테스트 케이스는 문제에서 설명한 상황이다. 두 승객이 역 3에서 만나 카드를 바꾼다. 두 번째 테스트 케이스에서는 두 승객이 만나지 않아 카드를 바꿀 수 없으므로 도시는 손해를 보지 않는다. 세 번째 테스트 케이스에서는 먼저 탄 승객 두 명 가운데 한 명만 나중에 탄 승객과 카드를 바꿀 수 있다.